Hồ sơ tội phạm

Mọi số nguyên không âm đều có biểu diễn trong hệ cơ số $k$. Ta gọi mỗi chữ số của biểu diễn đó là một k-it.

Với hai k-it $a$ và $b$, XOR cơ số k của chúng được định nghĩa là $(a+b)modk$.

XOR cơ số $k$ của hai số nguyên $a$ và $b$, ký hiệu $a{\oplus }_{k}b$, là số nhận được bằng cách lấy XOR cơ số $k$ trên từng cặp k-it tương ứng trong biểu diễn cơ số $k$ của $a$ và $b$ (số nào ngắn hơn được bổ sung các k-it $0$ ở phía trước). Chẳng hạn với $k=3$: $7=(21{)}_3$, $6=(20{)}_3$, và $(21{)}_3{\oplus }_3(20{)}_3=(11{)}_3=4$, tức $7{\oplus }_{3}6=4$.

Bạn đã xâm nhập được vào kho hồ sơ tội phạm của sở cảnh sát, nhưng còn thiếu mật khẩu. Mật khẩu là một số nguyên nằm trong đoạn $[0,n-1]$, và bạn được phép đoán nhiều nhất $n$ lần.

Điểm khó là hệ thống tự thay đổi mật khẩu sau mỗi lần đoán sai: nếu mật khẩu trước khi đoán là $x$ và bạn đoán số $y\ne x$, hệ thống đổi mật khẩu thành số $z$ thoả mãn $x{\oplus }_{k}z=y$.

Hãy tìm ra mật khẩu.

Bộ tương tác là thích ứng (adaptive): mật khẩu ban đầu không được cố định từ trước và có thể phụ thuộc vào các truy vấn của bạn, nhưng luôn đảm bảo tồn tại ít nhất một mật khẩu ban đầu trong $[0,n-1]$ nhất quán với mọi câu trả lời đã nhận.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ - số lượng bộ test.

Với mỗi bộ test, đọc vào hai số nguyên $n$ và $k$.

Tương tác

Với mỗi bộ test, sau khi đọc $n$ và $k$, bạn được hỏi nhiều nhất $n$ lần.

Mỗi lần hỏi, in ra một số nguyên $y$ ($0\le y\le 2·{10}^7$) rồi xoá bộ đệm (flush). Sau đó đọc vào một số nguyên $r$:

• $r=1$: bạn đoán đúng mật khẩu hiện tại, hãy chuyển sang bộ test tiếp theo.
• $r=0$: đoán sai, mật khẩu đã bị đổi theo quy tắc trên.
• $r=-1$: truy vấn không hợp lệ hoặc bạn đã vượt quá $n$ lần hỏi. Hãy kết thúc chương trình ngay lập tức.

Để flush, dùng fflush(stdout) hoặc cout.flush() trong C++, sys.stdout.flush() trong Python.

Ràng buộc

• $1\le t\le 10000$
• $1\le n\le 3·{10}^4$
• $2\le k\le 100$
• Tổng $n$ trên tất cả các bộ test không vượt quá $3·{10}^4$.
• Mỗi truy vấn phải thoả $0\le y\le 2·{10}^7$.

Ví dụ