Это интерактивная задача.

Менджи потерялся, и все по нему скучают. Ваша задача — найти его!

Дано двоичное дерево $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.

Обратите внимание, что интерактор является адаптивным: это означает, что ответ может меняться в зависимости от ваших запросов, пока он остаётся согласованным с ограничениями задачи и ответами на предыдущие запросы.

Гарантируется, что сумма $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