Detta är ett interaktivt problem.

Menji har gått vilse och alla saknar honom. Det är ditt jobb att hitta honom!

Det finns ett binärt träd $T$ som består av $n$ hörn, och varje kant i trädet $T$ har längden $1$. Menji gömmer sig i hörn $X$. Du känner till trädets struktur, men du vet inte vilket hörn som är $X$.

För att hitta $X$ kan du skicka signaler. Du kan välja ett hörn $u$ och en signalstyrka $k$, och sedan skicka en signal med styrka $k$ från hörn $u$. Om avståndet mellan $u$ och $X$ är högst $k$ kommer Menji att ta emot signalen och skicka tillbaka en signal, som du då tar emot. Annars tar du inte emot någonting.

Att skicka signaler går långsamt och du har bråttom, så bestäm Menjis position med högst $40$ signaler.

Interaktionsprotokoll

Indatan innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 100$), antalet testfall.

För varje testfall innehåller den första raden ett heltal $n$ ($2 \le n \le 3 \times 10^4$), antalet hörn i trädet.

Den andra raden innehåller $n - 1$ heltal $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), där $fa_i$ är föräldern till $i$ i trädet. Trädet är rotat i hörn $1$.

Det garanteras att trädet är ett binärt träd, det vill säga det existerar inte $1 < i < j < k \le n$ sådana att $fa_i = fa_j = fa_k$.

För att skicka en signal, skriv ut en enda rad i följande format:

• ? u k: Anger att du skapar en signal i hörn $u$ med styrka $k$. Du måste se till att $1 \le u \le n, 0 \le k \le n$. Därefter måste du läsa in ett heltal $o$ ($o \in \{0, 1\}$). Om du tog emot signalen, eller ekvivalent om $dis(u, X) \le k$, så är $o = 1$, annars är $o = 0$.

För att rapportera svaret, skriv ut en enda rad i följande format:

• ! u: Anger att du har kommit fram till att $X = u$. Du måste gå vidare till nästa testfall efter att ha skrivit ut detta, eller avsluta programmet om det inte finns fler.

För varje testfall får du skicka högst $40$ signaler. Att rapportera svaret räknas inte som att skicka en signal.

Om du skickar fler än $40$ signaler, om signalen du skickade är felformaterad eller om svaret du rapporterade är felaktigt, kommer interaktionen att avslutas och du får bedömningen Wrong answer.

Observera att interaktorn är adaptiv, vilket innebär att svaret kan ändras beroende på dina frågor så länge det förblir förenligt med begränsningarna och svaren på de tidigare frågorna.

Det garanteras att summan av $n$ över alla testfall inte överstiger $3 \times 10^4$.

Glöm inte att skriva ut radslut och tömma utdatabufferten (flush) efter varje rad du skriver ut. Du kan använda fflush(stdout) eller cout.flush() i C++, System.out.flush() i Java och stdout.flush() i Python.

Exempel

Exempelindata 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Exempelutdata 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3