이 문제는 인터랙티브 문제입니다.

Menji가 길을 잃어서 모두가 그를 그리워하고 있습니다. 그를 찾는 것이 여러분의 임무입니다!

$n$개의 정점으로 이루어진 이진 트리 $T$가 있으며, 트리 $T$의 각 간선의 길이는 $1$입니다. Menji는 정점 $X$에 숨어 있습니다. 여러분은 트리의 구조는 알고 있지만, $X$가 어디인지는 모릅니다.

$X$를 찾기 위해 신호를 보낼 수 있습니다. 정점 $u$와 신호 강도 $k$를 선택한 뒤, 정점 $u$에서 강도 $k$인 신호를 보낼 수 있습니다. $u$와 $X$ 사이의 거리가 $k$ 이하이면 Menji가 신호를 받고 다시 신호를 보내며, 여러분은 그 신호를 받게 됩니다. 그렇지 않으면 아무것도 받지 못합니다.

신호를 보내는 것은 느리고 시간이 촉박하므로, $40$번 이하의 신호 전송으로 Menji의 위치를 알아내십시오.

인터랙션 프로토콜

입력은 여러 개의 테스트 케이스를 포함합니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $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$입니다.

주어지는 트리는 이진 트리임이 보장됩니다. 즉, $fa_i = fa_j = fa_k$를 만족하는 $1 < i < j < k \le n$은 존재하지 않습니다.

신호를 보내려면 다음 형식으로 한 줄을 출력하십시오:

• ? 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 판정을 받게 됩니다.

인터랙터는 적응적(adaptive)임에 유의하십시오. 즉, 제약 조건 및 이전 질문들에 대한 답변과 모순되지 않는 한, 여러분의 질문에 따라 정답이 바뀔 수 있습니다.

모든 테스트 케이스에 걸친 $n$의 합이 $3 \times 10^4$을 초과하지 않음이 보장됩니다.

각 줄을 출력한 후에는 줄바꿈 문자를 출력하고 출력 버퍼를 비우는(flush) 것을 잊지 마십시오. 스트림을 비우기 위해 C++에서는 fflush(stdout) 또는 cout.flush(), Java에서는 System.out.flush(), Python에서는 stdout.flush()를 사용할 수 있습니다.

예제

예제 입력 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