Este es un problema interactivo.

Menji se ha perdido y todo el mundo lo echa de menos. ¡Tu trabajo es encontrarlo!

Hay un árbol binario $T$ que consta de $n$ vértices, y cada arista del árbol $T$ tiene longitud $1$. Menji está escondido en el vértice $X$. Conoces la estructura del árbol; sin embargo, no conoces $X$.

Para encontrar $X$, puedes enviar señales. Puedes elegir un vértice $u$ y una intensidad de señal $k$, y luego enviar una señal de intensidad $k$ desde el vértice $u$. Si la distancia entre $u$ y $X$ no es mayor que $k$, Menji recibirá la señal y enviará una señal de vuelta, y tú la recibirás. De lo contrario, no recibirás nada.

Enviar señales es lento y tienes prisa, así que determina la posición de Menji en no más de $40$ señales.

Protocolo de interacción

La entrada contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 100$), el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($2 \le n \le 3 \times 10^4$), el número de vértices en el árbol.

La segunda línea contiene $n - 1$ enteros $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), donde $fa_i$ es el padre de $i$ en el árbol. El árbol tiene su raíz en el vértice $1$.

Se garantiza que el árbol es un árbol binario, es decir, no existen $1 < i < j < k \le n$ tales que $fa_i = fa_j = fa_k$.

Para enviar una señal, imprime una sola línea con el siguiente formato:

• ? u k: Indica que creas una señal en el vértice $u$ con intensidad $k$. Debes asegurarte de que $1 \le u \le n, 0 \le k \le n$. Luego debes leer un entero $o$ ($o \in \{0, 1\}$). Si recibiste la señal, o equivalentemente $dis(u, X) \le k$, entonces $o = 1$; en caso contrario, $o = 0$.

Para informar la respuesta, imprime una sola línea con el siguiente formato:

• ! u: Indica que has encontrado $X = u$. Debes pasar al siguiente caso de prueba después de imprimir esto, o terminar si ya no hay más.

Para cada caso de prueba, puedes enviar como máximo $40$ señales. Informar la respuesta no cuenta como enviar una señal.

Si envías más de $40$ señales, o la señal enviada tiene un formato incorrecto, o la respuesta informada es incorrecta, la interacción terminará y recibirás el veredicto Wrong answer.

Ten en cuenta que el interactor es adaptativo, lo que significa que la respuesta puede cambiar dependiendo de tus consultas siempre que siga siendo consistente con las restricciones y con las respuestas a las consultas anteriores.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $3 \times 10^4$.

Después de imprimir cada línea, no olvides imprimir el salto de línea y vaciar el flujo de salida (flush). Puedes usar fflush(stdout) o cout.flush() en C++, System.out.flush() en Java y stdout.flush() en Python.

Ejemplo

Entrada de ejemplo 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Salida de ejemplo 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3