G. Fatalerror: Implementation Failed
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden non-negative integer $$$n$$$ ($$$0 \le n \lt 2^{64}$$$). Your task is to determine $$$n$$$ by asking queries of the following type:

  • Choose a non-negative integer $$$x$$$ ($$$0 \le x \lt 2^{64}$$$). The judge will respond with the number of set bits in the binary representation of $$$n \oplus x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. The number of set bits of a non-negative integer $$$x$$$ is the number of $$$1$$$s in its binary representation. For example, the binary representation of $$$13$$$ is $$$1011$$$, hence the number of set bits is $$$3$$$.

You may ask no more than $$$63$$$ queries.

Input

Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

Interaction

To ask a query, output a line in the following format:

  • ? x

where $$$x$$$ ($$$0 \le x \lt 2^{64}$$$) is the integer you asked.

After each query, you should read one line containing one integer, denoting the number of set bits of $$$n \oplus x$$$.

When you are ready to output the answer, output a line in the following format:

  • ! n

where $$$n$$$ ($$$0 \le n \lt 2^{64}$$$) is the hidden integer.

Note that printing the answer is not counted within the total number of queries.

The interactor is NOT adaptive, meaning that the answer is known before the participant asks the queries and does not depend on the queries asked by the participant.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
1

2

13
Output

? 0

? 114514

! 9
Note

In the first test case, the hidden integer is $$$9$$$.

In the first query, $$$x=0$$$. The binary representation of $$$9 \oplus 0 = 9$$$ is $$$1001$$$, with $$$2$$$ set bits. The judge responds with $$$2$$$.

In the second query, $$$x=114514$$$. The binary representation of $$$9 \oplus 114514 = 114523$$$ is $$$11011111101011011$$$, with $$$13$$$ set bits. The judge responds with $$$13$$$.