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

Ivan은 배틀쉽 게임에 새로운 규칙을 도입했습니다!

• 게임은 $n \times n$ 보드에서 진행됩니다.
• 첫 번째 플레이어는 정수 $k$ ($n \le k \le \lfloor \frac{n}{2} \rfloor^2$)를 선택합니다.
• 그 후, 첫 번째 플레이어는 $k$개의 배를 보드에 배치하여 배가 차지하는 칸의 수가 최대가 되도록 합니다 (모든 가능한 $k$개의 배 배치 방법 중에서).
• 각 배는 $1 \times a$ 또는 $a \times 1$ 크기의 직사각형이어야 합니다 ($a$는 $1$부터 $n$ 사이의 임의의 정수). 어떤 두 배도 (변이나 꼭짓점으로) 서로 인접해서는 안 됩니다.

그 후, 두 번째 플레이어가 게임을 시작합니다.

• 두 번째 플레이어는 보드의 크기 $n$만 알고 있습니다.
• 두 번째 플레이어는 다음과 같은 질의를 할 수 있습니다: 셀 $(x, y)$가 배에 의해 점유되어 있는가?
• 두 번째 플레이어는 보드에서 비어 있는 $2 \times 2$ 정사각형을 찾거나, 그러한 정사각형이 없음을 말해야 합니다.

두 번째 플레이어는 최대 $6n$번의 질의를 할 수 있습니다. 두 번째 플레이어가 되어 게임에서 승리하세요!

인터랙션 프로토콜

첫 번째 줄에는 단일 정수 $t$ ($1 \le t \le 100$)가 주어지며, 이는 진행할 게임의 수입니다. $t$번의 게임을 진행하고 그 후에 인터랙션을 종료해야 합니다.

게임 시작 시, 보드의 크기를 나타내는 단일 정수 $n$ ($3 \le n \le 1000$)이 주어집니다.

그 후, 질의를 할 수 있습니다. 질의를 하려면 한 줄에 "? x y" ($1 \le x, y \le n$)를 출력하세요. 이는 셀의 좌표입니다. 그러면 다음과 같은 답변 $c$를 받게 됩니다:

• $c = -1$인 경우, 너무 많은 질의를 했습니다. 프로그램을 종료해야 합니다.
• $c = 0$인 경우, 셀 $(x, y)$는 비어 있습니다.
• $c = 1$인 경우, 셀 $(x, y)$는 배에 의해 점유되어 있습니다.

게임을 마치려면 한 줄에 "! x y"를 출력하세요. 여기서:

• 보드에 비어 있는 $2 \times 2$ 정사각형이 없으면 $x = -1, y = -1$입니다.
• 그렇지 않은 경우, $1 \le x, y \le n - 1$이며 셀 $(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)$로 이루어진 정사각형이 비어 있어야 합니다.

답이 틀리면 값 -1이 포함된 줄을 받게 되며, 프로그램을 종료해야 합니다. 그렇지 않으면 값 1이 포함된 줄을 받게 되며, 다음 게임을 진행해야 합니다 (마지막 게임이었다면 프로그램을 종료하세요).

모든 게임에 대한 $n$의 합은 $5000$을 넘지 않음이 보장됩니다. 각 게임의 보드는 고정되어 있으며, 인터랙터는 적응형(adaptive)이 아님을 보장합니다. 출력을 하지 않거나 출력을 플러시(flush)하는 것을 잊으면 Idleness Limit Exceeded 판정을 받게 됩니다.

예제

입력 1

2
3
0
1
4
0
1
1

출력 1

? 2 1
! -1 -1
? 1 3
? 4 3
! 2 2

참고

첫 번째 테스트의 보드는 아래 그림과 같습니다. 행은 $x$ 좌표에, 열은 $y$ 좌표에 대응합니다.

첫 번째 게임의 보드. 두 번째 게임의 보드.

첫 번째 게임에서는 보드에 비어 있는 $2 \times 2$ 정사각형이 없습니다. 두 번째 게임에서는 보드에 정확히 하나의 비어 있는 $2 \times 2$ 정사각형이 있습니다.