Ini adalah soal interaktif.

Menji tersesat dan semua orang merindukannya. Tugas Anda adalah menemukannya!

Terdapat sebuah pohon biner $T$ yang terdiri dari $n$ simpul, dan setiap sisi dari pohon $T$ memiliki panjang $1$. Menji bersembunyi di simpul $X$. Anda mengetahui struktur pohon tersebut, namun Anda tidak mengetahui $X$.

Untuk menemukan $X$, Anda dapat mengirim sinyal. Anda dapat memilih sebuah simpul $u$ dan memilih kekuatan sinyal $k$, lalu mengirim sinyal berkekuatan $k$ dari simpul $u$. Jika jarak antara $u$ dan $X$ tidak lebih dari $k$, Menji akan menerima sinyal tersebut dan mengirim balik sebuah sinyal, sehingga Anda akan menerima sinyal. Jika tidak, Anda tidak akan menerima apa pun.

Mengirim sinyal membutuhkan waktu yang lama dan Anda sedang terburu-buru, jadi tentukanlah posisi Menji dalam paling banyak $40$ pengiriman sinyal.

Protokol Interaksi

Masukan memuat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$), banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($2 \le n \le 3 \times 10^4$), banyaknya simpul pada pohon.

Baris kedua berisi $n - 1$ bilangan bulat $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), dengan $fa_i$ adalah induk dari $i$ pada pohon. Pohon tersebut berakar di simpul $1$.

Dijamin bahwa pohon tersebut adalah pohon biner, artinya tidak ada $1 < i < j < k \le n$ sedemikian sehingga $fa_i = fa_j = fa_k$.

Untuk mengirim sinyal, cetak satu baris dengan format berikut:

• ? u k: Menyatakan bahwa Anda membuat sinyal di simpul $u$ dengan kekuatan $k$. Anda harus memastikan $1 \le u \le n, 0 \le k \le n$. Kemudian Anda harus membaca sebuah bilangan bulat $o$ ($o \in \{0, 1\}$). Jika Anda menerima sinyal, atau secara ekuivalen $dis(u, X) \le k$, maka $o = 1$; jika tidak, maka $o = 0$.

Untuk melaporkan jawaban, cetak satu baris dengan format berikut:

• ! u: Menyatakan bahwa Anda telah menemukan $X = u$. Anda harus melanjutkan ke kasus uji berikutnya setelah mencetak baris ini, atau menghentikan program jika tidak ada kasus uji lagi.

Untuk setiap kasus uji, Anda dapat mengirim paling banyak $40$ sinyal. Melaporkan jawaban tidak dihitung sebagai mengirim sinyal.

Jika Anda mengirim lebih dari $40$ sinyal, atau sinyal yang Anda kirim tidak sesuai format, atau jawaban yang Anda laporkan salah, maka interaksi akan berakhir dan Anda akan mendapatkan vonis Wrong answer.

Perhatikan bahwa interaktor bersifat adaptif, artinya jawaban dapat berubah tergantung pada kueri Anda selama tetap konsisten dengan batasan serta jawaban atas kueri-kueri sebelumnya.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $3 \times 10^4$.

Setelah mencetak setiap baris, jangan lupa untuk mencetak karakter akhir baris dan melakukan flush pada keluaran. Anda dapat menggunakan fflush(stdout) atau cout.flush() untuk C++, System.out.flush() untuk Java, dan stdout.flush() untuk Python.

Contoh

Contoh Masukan 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Contoh Keluaran 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3