問題文

yukimy32 さんは $2$ つの $10^6$ 以下の正整数 $N, M$ を隠し持っています。あなたは $10$ 回まで以下の質問を行うことができます。$N$ を特定してください。

• $1 \le A \le 10^6, 0 \le B \le 10^6$ を満たす整数 $A, B$ を出力してください。

  このとき、ジャッジは $\displaystyle \sum _{i=0}^{N-1} \left\lfloor \frac{Ai+B}{M} \right\rfloor$ を返します。

$T$ 個のテストケースが与えられるので、それぞれについて $N$ を特定してください。詳しくは、入出力をご覧ください。

制約

• 入力は全て整数
• $1 \le T \le 100$
• $1 \le N, M \le 10^6$

入出力

はじめ、入力にテストケース数 $T$ が以下の形式で与えられます。

$T$

その後 $T$ 回、以下の入出力を繰り返してください。

Step 1 (質問)

以下の形式で $A, B$ を出力してください。このとき、$1 \le A \le 10^6, 0 \le B \le 10^6$ を満たさなければいけません。

? $A$ $B$

その後、ジャッジは $\displaystyle R=\sum _{i=0}^{N-1} \left\lfloor \frac{Ai+B}{M} \right\rfloor$ を以下の形式で返すので、これを標準入力として受け取ってください。

$R$

これまでの質問で $N$ の値がわかった、または Step 1 を $10$ 回繰り返した場合、Step 2 に進んでください。

あなたの出力が正しくなかった (出力形式が正しくない、または $A, B$ が制約を満たしていない) 場合、ジャッジは $-1$ を返します。この場合は、ただちにプログラムを終了してください。

Step 2 (解答)

$10$ 回以下の Step 1 の質問で $N$ の値がわかった場合、以下の形式で $N$ の値を出力してください。

! $N$

この値が正しい場合ジャッジは $1$ を返すので、それを標準入力として受け取り、次のテストケースの Step 1 に戻ってください。この値が正しくなかった場合、ジャッジは $-1$ を返します。この場合と、最後のテストケースだった場合はただちにプログラムを終了してください。

注意

出力を行う場合、毎回標準出力を flush してください。不正な出力をして $-1$ を標準入力として受け取った場合、ただちにプログラムを終了してください。これらを行わない場合、正しい受け答えをしていても TLE になることがあります。

また、ジャッジは適応的ではありません。

サンプル

以下は WA となる受け答えの一例です。