هذه مسألة تفاعلية.

لقد تاه مينجي والجميع يفتقدونه. مهمتك هي العثور عليه!

توجد شجرة ثنائية $T$ تتكون من $n$ من الرؤوس، وطول كل ضلع في الشجرة $T$ يساوي $1$. يختبئ مينجي عند الرأس $X$. أنت تعرف بنية الشجرة، لكنك لا تعرف $X$.

للعثور على $X$، يمكنك إرسال إشارات. يمكنك اختيار رأس $u$ واختيار قوة إشارة $k$، ثم إرسال إشارة بقوة $k$ من الرأس $u$. إذا كانت المسافة بين $u$ و $X$ لا تتجاوز $k$، فسيتلقى مينجي الإشارة ويرسل إشارة في المقابل، وستتلقى أنت تلك الإشارة. وإلا فلن تتلقى أي شيء.

إرسال الإشارات بطيء وأنت في عجلة من أمرك، لذا يُرجى تحديد موقع مينجي بما لا يزيد عن $40$ إشارة.

بروتوكول التفاعل

يحتوي الإدخال على عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح $T$ ($1 \le T \le 100$)، وهو عدد حالات الاختبار.

لكل حالة اختبار، يحتوي السطر الأول على عدد صحيح $n$ ($2 \le n \le 3 \times 10^4$)، وهو عدد الرؤوس في الشجرة.

يحتوي السطر الثاني على $n - 1$ من الأعداد الصحيحة $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$)، حيث $fa_i$ هو الأب للرأس $i$ في الشجرة. جذر الشجرة هو الرأس $1$.

من المضمون أن الشجرة هي شجرة ثنائية، أي أنه لا يوجد $1 < i < j < k \le n$ بحيث يكون $fa_i = fa_j = fa_k$.

لإرسال إشارة، اطبع سطراً واحداً بالصيغة التالية:

• ? 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$.

للإبلاغ عن الإجابة، اطبع سطراً واحداً بالصيغة التالية:

• ! u: للإشارة إلى أنك وجدت أن $X = u$. يجب عليك الانتقال إلى حالة الاختبار التالية بعد طباعة هذا السطر، أو إنهاء البرنامج إذا لم يتبقَّ المزيد من حالات الاختبار.

لكل حالة اختبار، يمكنك إرسال $40$ إشارة على الأكثر. الإبلاغ عن الإجابة لا يُحتسب كإرسال إشارة.

إذا أرسلت أكثر من $40$ إشارة، أو كانت الإشارة التي أرسلتها غير صالحة الصيغة، أو كانت الإجابة التي أبلغت عنها غير صحيحة، فسينتهي التفاعل وستحصل على حكم Wrong answer.

لاحظ أن المتفاعل تكيفي (adaptive)، مما يعني أن الإجابة قد تتغير اعتماداً على استعلاماتك طالما بقيت متسقة مع القيود ومع الإجابات عن الاستعلامات السابقة.

من المضمون أن مجموع $n$ عبر جميع حالات الاختبار لا يتجاوز $3 \times 10^4$.

بعد طباعة كل سطر، لا تنسَ طباعة نهاية السطر وتفريغ مجرى الإخراج (flush). يمكنك استخدام fflush(stdout) أو cout.flush() لتفريغ المجرى في C++، واستخدام System.out.flush() في Java، و stdout.flush() في Python.

مثال

مثال للإدخال 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