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$。 保证每局游戏中的棋盘是固定的，且交互器是非自适应的。 如果你没有输出任何内容或忘记刷新输出，你的程序将获得 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$ 正方形。