Dette er en interaktiv oppgave.

Menji har gått seg bort, og alle savner ham. Det er din jobb å finne ham!

Det finnes et binært tre $T$ som består av $n$ noder, og hver kant i treet $T$ har lengde $1$. Menji gjemmer seg ved node $X$. Du kjenner strukturen til treet, men du vet ikke hvilken node som er $X$.

For å finne $X$ kan du sende signaler. Du kan velge en node $u$ og en signalstyrke $k$, og deretter sende et signal med styrke $k$ fra node $u$. Hvis avstanden mellom $u$ og $X$ ikke er større enn $k$, vil Menji motta signalet og sende et signal tilbake, slik at du mottar signalet. Ellers vil du ikke motta noe.

Å sende signaler går sakte og du har det travelt, så finn posisjonen til Menji med høyst $40$ signaler.

Interaksjonsprotokoll

Inndataene inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 100$), antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et heltall $n$ ($2 \le n \le 3 \times 10^4$), antallet noder i treet.

Den andre linjen inneholder $n - 1$ heltall $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), der $fa_i$ er forelderen til $i$ i treet. Treet har rot i node $1$.

Det er garantert at treet er et binært tre, det vil si at det ikke finnes $1 < i < j < k \le n$ slik at $fa_i = fa_j = fa_k$.

For å sende et signal skal du skrive ut én enkelt linje på følgende format:

• ? u k: Angir at du oppretter et signal ved node $u$ med styrke $k$. Du må sørge for at $1 \le u \le n, 0 \le k \le n$. Deretter må du lese et heltall $o$ ($o \in \{0, 1\}$). Hvis du mottok signalet, eller ekvivalent at $dis(u, X) \le k$, så er $o = 1$, ellers er $o = 0$.

For å rapportere svaret skal du skrive ut én enkelt linje på følgende format:

• ! u: Angir at du har funnet $X = u$. Du må gå videre til neste testtilfelle etter å ha skrevet ut dette, eller avslutte hvis det ikke er flere.

For hvert testtilfelle kan du sende høyst $40$ signaler. Å rapportere svaret teller ikke som å sende et signal.

Hvis du sender flere enn $40$ signaler, eller signalet du sendte har feil format, eller svaret du rapporterte er feil, vil interaksjonen avsluttes og du vil få dommen Wrong answer.

Merk at interaktoren er adaptiv, noe som betyr at svaret kan endre seg avhengig av spørringene dine så lenge det forblir konsistent med betingelsene og svarene på de tidligere spørringene.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $3 \times 10^4$.

Etter å ha skrevet ut hver linje må du ikke glemme å skrive ut linjeskift og tømme utdatabufferen (flush). Du kan bruke fflush(stdout) eller cout.flush() i C++, System.out.flush() i Java og stdout.flush() i Python.

Eksempel

Eksempelinndata 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Eksempelutdata 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3