This is an interactive problem.

While traveling the multiverse, Hanbyeol lost her teleportation skill and soon discovered that Eunha had it! To regain her teleportation skill, Hanbyeol decided to make a bet with Eunha as follows.

Eunha has prepared two hidden integers $N$ and $K$, which only she knows and satisfies $1 \le N, K < 10^8$. Hanbyeol can ask Eunha up to $Q$ questions of the following form:

• ? $x$ $y$: Is $N \times K^x \equiv N \times K^y \pmod{10^8}$ true?

Hanbyeol needs to find the smallest value of $b$ among two distinct non-negative integers $a$ and $b$ that satisfy $N \times K^a \equiv N \times K^b \pmod{10^8}$, while minimizing $a$. Eunha chooses $N$ and $K$ such that there is always such a $b$ for a fair bet. Hanbyeol asks you to write a program to help her win this bet.

Interaction

Your program should interact with the interactor through standard input and standard output as follows.

The input consists of one or more test cases. First, the number of test cases $T$ is given. For each test case, you must interact as follows:

By printing the query below, you will receive a response on the next line. If the answer to the query is true, YES will be given; if false, NO will be given. This query can be used a maximum of $Q$ times within a single test case.

• ? $x$ $y$ (where $0 \le x, y \le 10^9$; $x, y$ are integers)

You can submit the answer by printing the following query. This query does not count as a question. The interaction for this test case ends immediately after printing this query.

• ! $b$

If the interaction for the previous test case has ended, you must immediately move on to the interaction for the next test case. If the interaction for the last test case has ended, you must immediately terminate the program.

For each test case, if the submitted answer is correct for all test cases, you will receive Accepted; if at least one of them is incorrect, you will receive Wrong Answer. However, unexpected results may happen if you do not print the solution through proper interactions in the limitations of the problem provided.

Constraints

• $1 \le T \le 100$

Scoring

Examples

Input 1

1
4
64 50
21 15
8 5
33413900 34653426

Output 1

5
24
16
631

Note

In the first test case, $N=21;$ $K=15$.

In the second test case, $N=33\, 413\, 900;$ $K=34\, 653\, 426$.

You must flush the output immediately after printing something. To flush you can use:

• C --- fflush(stdout)
• C++ --- std::cout.flush()
• Python --- sys.stdout.flush()
• Java --- System.out.flush()
• read the documentation for other languages.

Also, note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction.