Dies ist ein interaktives Problem.

Menji hat sich verlaufen und alle vermissen ihn. Es ist deine Aufgabe, ihn zu finden!

Es gibt einen Binärbaum $T$, der aus $n$ Knoten besteht, und jede Kante des Baums $T$ hat die Länge $1$. Menji versteckt sich bei Knoten $X$. Du kennst die Struktur des Baums, weißt aber nicht, welcher Knoten $X$ ist.

Um $X$ zu finden, kannst du Signale senden. Du kannst einen Knoten $u$ und eine Signalstärke $k$ wählen und dann ein Signal der Stärke $k$ von Knoten $u$ aus senden. Wenn der Abstand zwischen $u$ und $X$ höchstens $k$ beträgt, empfängt Menji das Signal und sendet ein Signal zurück, das du wiederum empfängst. Andernfalls empfängst du nichts.

Das Senden von Signalen dauert lange und du hast es eilig. Bestimme daher bitte die Position von Menji mit höchstens $40$ Signalen.

Interaktionsprotokoll

Die Eingabe enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die Anzahl der Testfälle.

Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($2 \le n \le 3 \times 10^4$), die Anzahl der Knoten im Baum.

Die zweite Zeile enthält $n - 1$ ganze Zahlen $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), wobei $fa_i$ der Elternknoten von $i$ im Baum ist. Der Baum ist bei Knoten $1$ gewurzelt.

Es ist garantiert, dass der Baum ein Binärbaum ist, d. h., es gibt keine $1 < i < j < k \le n$ mit $fa_i = fa_j = fa_k$.

Um ein Signal zu senden, gib eine einzelne Zeile im folgenden Format aus:

• ? u k: Gibt an, dass du bei Knoten $u$ ein Signal mit Stärke $k$ erzeugst. Du musst sicherstellen, dass $1 \le u \le n, 0 \le k \le n$ gilt. Anschließend musst du eine ganze Zahl $o$ ($o \in \{0, 1\}$) einlesen. Wenn du das Signal empfangen hast, oder äquivalent dazu $dis(u, X) \le k$ gilt, ist $o = 1$, andernfalls $o = 0$.

Um die Antwort zu melden, gib eine einzelne Zeile im folgenden Format aus:

• ! u: Gibt an, dass du $X = u$ herausgefunden hast. Nach dieser Ausgabe musst du mit dem nächsten Testfall fortfahren oder das Programm beenden, falls keine weiteren Testfälle folgen.

Für jeden Testfall darfst du höchstens $40$ Signale senden. Das Melden der Antwort zählt nicht als Senden eines Signals.

Wenn du mehr als $40$ Signale sendest, das gesendete Signal ein ungültiges Format hat oder die gemeldete Antwort falsch ist, wird die Interaktion beendet und du erhältst das Urteil Wrong answer.

Beachte, dass der Interaktor adaptiv ist, was bedeutet, dass sich die Antwort in Abhängigkeit von deinen Abfragen ändern kann, solange sie mit den Bedingungen und den Antworten auf vorherige Abfragen konsistent bleibt.

Es ist garantiert, dass die Summe von $n$ über alle Testfälle hinweg $3 \times 10^4$ nicht überschreitet.

Vergiss nach der Ausgabe jeder Zeile nicht, einen Zeilenumbruch auszugeben und den Ausgabepuffer zu leeren (flush). Du kannst fflush(stdout) oder cout.flush() in C++, System.out.flush() in Java und stdout.flush() in Python verwenden.

Beispiel

Beispieleingabe 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Beispielausgabe 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3