CF1483E.Vabank

Gustaw is the chief bank manager in a huge bank. He has unlimited access to the database system of the bank, in a few clicks he can move any amount of money from the bank's reserves to his own private account. However, the bank uses some fancy AI fraud detection system that makes stealing more difficult.

Gustaw knows that the anti-fraud system just detects any operation that exceeds some fixed limit $M$ euros and these operations are checked manually by a number of clerks. Thus, any fraud operation exceeding this limit is detected, while any smaller operation gets unnoticed.

Gustaw doesn't know the limit $M$ and wants to find it out. In one operation, he can choose some integer $X$ and try to move $X$ euros from the bank's reserves to his own account. Then, the following happens.

• If $X \le M$, the operation is unnoticed and Gustaw's account balance raises by $X$ euros.
• Otherwise, if $X \gt M$, the fraud is detected and cancelled. Moreover, Gustaw has to pay $X$ euros from his own account as a fine. If he has less than $X$ euros on the account, he is fired and taken to the police.

Initially Gustaw has $1$ euro on his account. Help him find the exact value of $M$ in no more than $105$ operations without getting him fired.

古斯塔夫是一家大型银行的首席经理。他对银行的数据库系统拥有无限访问权限，只需几次点击，他就能将任意数额的资金从银行储备金转移到自己的私人账户中。然而，银行采用了一套先进的AI反欺诈系统，使得盗窃行为变得更加困难。

古斯塔夫知道，该反欺诈系统仅会检测任何超过某个固定阈值 $M$ 欧元的操作，而这些被检测到的操作将由若干名职员进行人工审核。因此，任何超过该阈值 $M$ 的欺诈操作都会被发现，而所有小于等于 $M$ 的操作则不会被察觉。

古斯塔夫并不知道阈值 $M$ 的具体数值，他希望确定其精确值。在一次操作中，他可以选择某个整数 $X$，并尝试将 $X$ 欧元从银行储备金转入自己的账户。随后，以下情况之一会发生：

• 若 $X \le M$，该操作不会被察觉，古斯塔夫的账户余额增加 $X$ 欧元；
• 否则，若 $X > M$，欺诈行为被发现并取消。此外，古斯塔夫须从自己账户中支付 $X$ 欧元作为罚金；若其账户余额不足 $X$ 欧元，则他将被立即解雇并移交警方。

初始时，古斯塔夫的账户余额为 $1$ 欧元。请帮助他在不超过 $105$ 次操作的前提下，准确找出 $M$ 的值，且确保他不被解雇。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

For each test case, there is no input prior to your first query, but you can be sure that $M$ is integer, and $0 \le M \le 10^{14}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。

对于每个测试用例，在你发出第一个查询之前没有输入，但你可以确定 $M$ 是一个整数，且 $0 \le M \le 10^{14}$。

For each test case, when you know the exact value of $M$, print a single line with format "! $M$". After that your program should proceed to the next test case or terminate, if it is the last one.

对于每个测试用例，当你确定了 $M$ 的精确值后，请输出一行，格式为 “! $M$”。之后，你的程序应继续处理下一个测试用例；若当前已是最后一个测试用例，则直接终止。

In the example $M = 5$, so the operation with $X = 6$ is detected. At this moment, Gustaw's balance is $16$ euros, so he just pays fine.

在示例中，$M = 5$，因此检测到 $X = 6$ 的操作。此时，古斯塔夫的余额为 $16$ 欧元，因此他只需缴纳罚款。