CF1999G2 Ruler (hard version)

本题是问题的困难版本。该版本与简单版之间的唯一区别是在这个版本中，你最多可以进行 $7$ 次查询。 这是一道交互题。 有一把有 $1001$ 个刻度的尺子，刻度分别为 $1 \sim 1001$。不幸的是，尺子丢失了一个刻度 $x$（$2 \le x \le 999$）。当你用尺子量一个长度为 $y$ 的物体时，尺子量出的结果为： - 若 $y < x$，尺子将会量出正确的结果 $y$。 - 否则，尺子将会量出错误的结果 $y + 1$。 你需要找出丢失的刻度 $x$。你可以每次提供两个 $1$ 至 $1000$ 内的整数 $a,b$，你将会收到尺子量出的 $a$ 的长度与尺子量出的 $b$ 的长度之积。 你可以进行最多 $7$ 次询问。

输入共一行一个整数 $T$，代表数据组数。

你可以输出 `? a b` 以进行一次询问。`a` 和 `b` 的含义见上。随后，你将收到一个整数，表示尺子量出的 $a$ 的长度与尺子量出的 $b$ 的长度之积。 当你猜出 $x$ 后，你需要输出一行 `! x`，`x` 为你猜出的 $x$ 值。 如果你的询问大于 $7$ 次或猜出的 $x$ 值不对，你将收到一行一个 `-1`。请立刻终止程序。 在进行一次询问后，你需要刷新缓冲区。否则，你可能会获得 ILE（Idleness Limit Exceeded）。刷新缓冲区方法如下： - 对于 C++：`fflush(stdout)` 或 `cout.flush()`； - 对于 Java：`System.out.flush()`； - 对于 Pascal：`flush(output)`； - 对于 Python：`stdout.flush()`。 Translated by liuli688

In the first test, the interaction proceeds as follows. SolutionJuryExplanation $ \texttt{2} $ There are 2 test cases. $ \texttt{? 3 5} $ $ \texttt{18} $ Secretly, the jury picked $ x=4 $ . The solution requests the $ 3 \times 5 $ rectangle, and the jury responds with $ 3 \times 6 = 18 $ , as described in the statement. $ \texttt{? 4 4} $ $ \texttt{25} $ The solution requests the $ 4 \times 4 $ rectangle, which the jury measures as $ 5 \times 5 $ and responds with $ 25 $ . $ \texttt{! 4} $ The solution has somehow determined that $ x=4 $ , and outputs it. Since the output is correct, the jury continues to the next test case. $ \texttt{? 99 100} $ $ \texttt{1} $ Secretly, the jury picked $ x=100 $ . The solution requests the $ 99 \times 100 $ rectangle, which the jury measures as $ 99 \times 101 $ and responds with $ 9999 $ . $ \texttt{! 100} $ The solution has somehow determined that $ x=100 $ , and outputs it. Since the output is correct and there are no more test cases, the jury and the solution exit.Note that the line breaks in the example input and output are for the sake of clarity, and do not occur in the real interaction.