Background

Falling cherry blossoms do not wait for spring. If you miss this chance, you may have to wait until the spring-to-summer season when wisteria blooms to enjoy the flowers.
But the two of them still have no mood to sit and feast under the cherry trees.

Because unknown floating spirits suddenly appear and disappear in front of them.
Only later did they understand that these unknown spirits drifting around are neither ordinary ghosts nor the vengeful spirits that appeared some time ago.
They are divine spirits. Spirits that should have transcended to become gods.

Generally speaking, divine spirits mostly live in shrines, but in fact they are formless spirits that can be seen everywhere.
These divine spirits leave them very confused.

Extraordinary and intense human desires, thoughts, fears, and emotions are the reason divine spirits appear. Generally, divine spirits rarely harm humans unless there is a strong desire. For example, praying for a good harvest, or asking to ward off disasters and evil, will not create divine spirits...

A small divine spirit guides Reimu and Marisa deep into the underground of Myouren Temple, where they fight an enemy revived after a thousand years. From the Myouren Temple graveyard to the Hall of Dreams Great Mausoleum in the middle of the lotus pond, from wandering dead spirits to the legendary Prince Shoutoku, from desire acceleration to a tiny desire-filled starry sky, everything feels so unbelievable.

"Only after death can one obtain an even more brilliant rebirth."

Problem Description

[This is an interactive problem.]

Let $f(x)$ be the smallest perfect square strictly greater than $x$, and let $g(x)$ be the largest perfect square less than or equal to $x$. For example, $f(1)=f(2)=g(4)=g(8)=4$.

A positive integer is "cute" if and only if $x-g(x)<f(x)-x$. For example, $1,5,11$ are cute positive integers, while $3,8,15$ are not.

To listen to the small divine spirit's wish, the protagonists need to ask Miko. The small divine spirit has a favorite positive integer $a$. Based on $x$ given by Reimu $\quad(x\in[0,10^9])$, Miko can ask the small divine spirit, and the small divine spirit can only answer whether $a+x$ is a cute positive integer ($\text{cute number}$).

Please find $a$ through appropriate queries.

Input Format

The first line contains a positive integer $T$, the number of test cases. Each test case is independent.

Then, for each test case, you may perform the following two operations:

• $\verb!? x!$: Ask whether $a+x$ is a $\text{cute number}$. Note that $x$ must be within $[0,10^9]$. For a valid query, the interactive judge returns a number $1$ or $0$, indicating that $a+x$ is / is not a $\text{cute number}$.
• $\verb|! a|$: Report the $a$ you have found. If your reported $a$ is correct, this test case ends. Note: the report operation is not counted toward the total number of queries.

If the number of your queries exceeds $100$, or $x$ is out of range, or the $a$ you report is incorrect, the interactive judge returns $-1$. In this case, you should terminate your program immediately, otherwise unpredictable errors may occur.

1

1

1

1

1

1

0

0

1

? 0

? 1

? 2

? 3

? 10

? 100

? 233

? 1919810

! 114514

Hint

Sample Explanation

The process in the sample is for reference only.

In the sample, $a=114514$, and it is a $\text{cute number}$ (because $338^2\le 114514 <339^2$, and $114514-338^2=270<339^2-114514=407$).

Similarly, $a+0,a+1,a+2,a+3,a+10$ are all $\text{cute number}$. But $a+100=114614$ is not a $\text{cute number}$, because $338^2\le 114614 <339^2$, and $114614-338^2=370\ge 339^2-114614=307$.

Constraints and Notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{a\le } & \bm{T\le} & \textbf{Special Property} & \textbf{Points}\\\hline 1 & 100 & 100 & - & 10\\\hline 3 & 10^9 & 2\times 10^3 & - & 20\\\hline 2 & 10^{12} & 2\times 10^3 & \textbf{A} & 30\\\hline 4 & 10^{12} & 2\times 10^3 & - & 40\\\hline \end{array}$$

Special Property $\textbf{A}$: It is guaranteed that $a$ is a $\text{cute number}$.

For all testdata, it is guaranteed that $1\le a\le 10^{12}$. In your queries, the value of $x$ must be within $[0,10^9]$.

---

In addition, your score for each test point is also related to the maximum number of queries used on that test point. Specifically, suppose on some test point you perform the query operation a total of $\text{max\_count}$ times.

• If $\text{max\_count}< 64$, you will get $100\%$ of the score for that test point.
• If $64\le \text{max\_count}< 81$, you will get $50\%$ of the score for that test point.
• If $81\le \text{max\_count}< 100$, you will get $20\%$ of the score for that test point.
• If $\text{max\_count}\ge 100$, you will not get any score for that test point.

Translated by ChatGPT 5