これはインタラクティブ問題です。

Menji が迷子になってしまい、みんな彼を恋しがっています。あなたの仕事は彼を見つけ出すことです！

$n$ 個の頂点からなる二分木 $T$ があり、木 $T$ の各辺の長さは $1$ です。Menji は頂点 $X$ に隠れています。あなたは木の構造を知っていますが、$X$ は知りません。

$X$ を見つけるために、信号を送ることができます。頂点 $u$ と信号強度 $k$ を選び、頂点 $u$ から強度 $k$ の信号を送ることができます。$u$ と $X$ の間の距離が $k$ 以下であれば、Menji は信号を受け取って信号を返し、あなたはその信号を受け取ります。そうでなければ、何も受け取りません。

信号の送信には時間がかかり、あなたは急いでいるため、$40$ 回以内の信号送信で Menji の位置を特定してください。

インタラクションプロトコル

入力は複数のテストケースを含みます。入力の最初の行には、テストケースの個数を表す整数 $T$（$1 \le T \le 100$）が含まれます。

各テストケースについて、最初の行には木の頂点数を表す整数 $n$（$2 \le n \le 3 \times 10^4$）が含まれます。

2行目には $n - 1$ 個の整数 $fa_2, fa_3, \dots, fa_n$（$1 \le fa_i < i$）が含まれます。ここで $fa_i$ は木における頂点 $i$ の親です。木は頂点 $1$ を根としています。

この木は二分木であること、すなわち $fa_i = fa_j = fa_k$ となるような $1 < i < j < k \le n$ は存在しないことが保証されています。

信号を送るには、以下の形式で1行出力してください：

• ? u k：頂点 $u$ で強度 $k$ の信号を発することを表す。$1 \le u \le n, 0 \le k \le n$ を満たす必要がある。その後、整数 $o$（$o \in \{0, 1\}$）を読み込む。信号を受け取った場合、すなわち $dis(u, X) \le k$ の場合は $o = 1$ であり、そうでない場合は $o = 0$ である。

答えを報告するには、以下の形式で1行出力してください：

• ! u：$X = u$ を見つけたことを表す。これを出力した後は次のテストケースに進み、これ以上テストケースがない場合はプログラムを終了する必要がある。

各テストケースについて、信号は最大で $40$ 回まで送ることができます。答えの報告は信号の送信回数には含まれません。

$40$ 回を超えて信号を送った場合、送った信号の形式が不正な場合、あるいは報告した答えが誤っている場合、インタラクションは終了し、Wrong answer の判定を受け取ります。

インタラクタは適応的（adaptive）であることに注意してください。つまり、制約および過去の質問への回答と矛盾しない限り、あなたの質問に応じて答えが変化する可能性があります。

すべてのテストケースにおける $n$ の総和が $3 \times 10^4$ を超えないことが保証されています。

各行を出力した後は、改行を出力し、出力ストリームをフラッシュ（flush）することを忘れないでください。ストリームをフラッシュするには、C++ では fflush(stdout) または cout.flush()、Java では System.out.flush()、Python では stdout.flush() を使用できます。

入出力例

入力例 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

出力例 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3