問題文

この問題はインタラクティブ問題です。
この問題では一つの入力につきテストケースが $T$ 個与えられます。

問題概要：
剰余類環 $\mathbb{Z}/N\mathbb{Z}$ の各要素が円環上に並んでいます。 ただし、 $N$ は与えられず、各要素にはランダムな値が割り振られています。 $2$ つの要素の和の冪乗を $Q$ 回まで質問することができるので $1$ に対応する値を特定してください。 ここで、 $2$ つの要素は $0$ に対応する値から時計回りで何番目という形式で指定することができます。

厳密な問題文：
正整数 $N$ があります。 $N$ はジャッジによって隠されています。

ジャッジは以下の手順で順列 $A$ と非負整数列 $B$ を生成します。生成される $A$ と $B$ は各テストケースごとに固定されており、変化することはありません。

• $\left(0,1,\dots,N-1\right)$ の順列 $\left(A_0,A_1,\dots,A_{N-1}\right)$ を $A_0=0$ となるように生成し、 $A$ とする。
• $10^9$ 以下の非負整数からなる数列 $(B_0,B_1,\dots,B_{N-1})$ を $B_i,(0\le i<N)$ が全て異なるように生成し、$B$ とする。

あなたは以下の質問を $Q$ 回まで行うことができます。

• $0\le i\le 10^9,\,0\le j\le 10^9,\,2\le k\le 10^9$ を満たす整数の組 $(i,j,k)$ を指定する。ジャッジは $x=\left(A_{i\bmod N}+A_{j\bmod N}\right)^k\bmod N$ として $B_x$ を出力する。ここで、 $a\bmod N$ は $a$ を $N$ で割った余りである。

$B_1$ を特定してください。

制約

• 入力は全て整数
• $1\le T\le 5$
• $2\le N\le 10^6$
• $Q=1600$

入出力

最初に、テストケースの数 $T$ が標準入力から与えられます。

$T$

以降、 $T$ 個のテストケースが続きます。

あなたは質問を行うことができます。以下の形式で標準出力に出力してください。

? $i$ $j$ $k$

質問に対する応答は次の形式で標準入力から与えられます。

$B_x$

ただし、質問の形式や制約が間違っているか質問回数が $Q$ 回を超えた場合、代わりに -1 が標準入力から与えられます。この場合、直ちにプログラムを終了させてください。

$B_1$ を特定できた場合、次の形式で標準出力に出力してください。

! $B_1$

その後、次のテストケースがあれば続けて処理し、なければすぐにプログラムを終了してください。

各出力の末尾には改行を付け、標準出力を flush してください。

サンプル

$T=2$ とした場合、以下のようなやり取りが考えられます。