To jest zadanie interaktywne.

Menji się zgubił i wszyscy za nim tęsknią. Twoim zadaniem jest go odnaleźć!

Dane jest drzewo binarne $T$ składające się z $n$ wierzchołków, a każda krawędź drzewa $T$ ma długość $1$. Menji ukrywa się w wierzchołku $X$. Znasz strukturę drzewa, ale nie znasz wierzchołka $X$.

Aby znaleźć $X$, możesz wysyłać sygnały. Możesz wybrać wierzchołek $u$ oraz siłę sygnału $k$, a następnie wysłać sygnał o sile $k$ z wierzchołka $u$. Jeśli odległość między $u$ a $X$ wynosi co najwyżej $k$, Menji odbierze sygnał i odeśle sygnał zwrotny, który Ty odbierzesz. W przeciwnym razie nie odbierzesz niczego.

Wysyłanie sygnałów jest powolne, a bardzo Ci się spieszy, dlatego wyznacz pozycję Menjiego, wysyłając nie więcej niż $40$ sygnałów.

Protokół interakcji

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 3 \times 10^4$), oznaczającą liczbę wierzchołków w drzewie.

Drugi wiersz zawiera $n - 1$ liczb całkowitych $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), gdzie $fa_i$ jest ojcem wierzchołka $i$ w drzewie. Drzewo jest ukorzenione w wierzchołku $1$.

Gwarantowane jest, że drzewo jest drzewem binarnym, to znaczy nie istnieją takie $1 < i < j < k \le n$, że $fa_i = fa_j = fa_k$.

Aby wysłać sygnał, wypisz pojedynczy wiersz w następującym formacie:

• ? u k: Oznacza wygenerowanie sygnału w wierzchołku $u$ o sile $k$. Musisz zadbać o to, by $1 \le u \le n, 0 \le k \le n$. Następnie musisz wczytać liczbę całkowitą $o$ ($o \in \{0, 1\}$). Jeśli odebrałeś sygnał, czyli równoważnie $dis(u, X) \le k$, to $o = 1$, a w przeciwnym razie $o = 0$.

Aby zgłosić odpowiedź, wypisz pojedynczy wiersz w następującym formacie:

• ! u: Oznacza, że ustaliłeś $X = u$. Po wypisaniu tego wiersza musisz przejść do kolejnego przypadku testowego lub zakończyć działanie programu, jeśli nie ma więcej przypadków.

W każdym przypadku testowym możesz wysłać co najwyżej $40$ sygnałów. Zgłoszenie odpowiedzi nie wlicza się do liczby wysłanych sygnałów.

Jeśli wyślesz więcej niż $40$ sygnałów, wysłany sygnał będzie miał niepoprawny format lub zgłoszona odpowiedź będzie błędna, interakcja zakończy się i otrzymasz werdykt Wrong answer.

Zauważ, że interaktor jest adaptacyjny, co oznacza, że odpowiedź może zmieniać się w zależności od Twoich zapytań, o ile pozostaje spójna z ograniczeniami oraz z odpowiedziami na wcześniejsze zapytania.

Gwarantowane jest, że suma $n$ we wszystkich przypadkach testowych nie przekracza $3 \times 10^4$.

Po wypisaniu każdego wiersza nie zapomnij wypisać znaku końca wiersza i opróżnić bufora wyjścia (flush). Możesz użyć fflush(stdout) lub cout.flush() w C++, System.out.flush() w Javie oraz stdout.flush() w Pythonie.

Przykład

Przykładowe wejście 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Przykładowe wyjście 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3