Це інтерактивна задача.

Менджі загубився, і всі за ним сумують. Ваше завдання — знайти його!

Дано двійкове дерево $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