Ivan đã nghĩ ra những quy tắc mới cho trò chơi tàu chiến!

• Trò chơi được chơi trên một bảng $n \times n$.
• Người chơi thứ nhất chọn một số nguyên $k$ ($n \le k \le \lfloor \frac{n}{2} \rfloor^2$).
• Sau đó, người chơi thứ nhất đặt $k$ con tàu lên bảng sao cho tổng số ô bị chiếm bởi các con tàu là lớn nhất có thể (trong số tất cả các cách đặt $k$ con tàu hợp lệ với mọi kích thước).
• Mỗi con tàu phải là một hình chữ nhật có kích thước $1 \times a$ hoặc $a \times 1$ ($a$ là bất kỳ số nguyên nào từ $1$ đến $n$). Hai con tàu bất kỳ không được có các ô lân cận (theo cạnh hoặc theo góc).

Sau đó, người chơi thứ hai bắt đầu lượt chơi của mình.

• Người chơi thứ hai chỉ biết kích thước của bảng là $n$.
• Người chơi thứ hai có thể đặt câu hỏi: ô $(x, y)$ có bị chiếm bởi con tàu nào không?
• Người chơi thứ hai cần tìm bất kỳ hình vuông $2 \times 2$ trống nào trên bảng, hoặc thông báo rằng không có hình vuông như vậy.

Người chơi thứ hai có thể hỏi tối đa $6n$ câu hỏi. Hãy đóng vai người chơi thứ hai và giành chiến thắng trong trò chơi!

Giao thức tương tác

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 100$) — số lượng trò chơi cần thực hiện. Bạn phải chơi $t$ trò chơi và kết thúc tương tác sau đó.

Khi bắt đầu mỗi trò chơi, bạn được cung cấp một số nguyên duy nhất $n$ ($3 \le n \le 1000$) — kích thước của bảng.

Sau đó, bạn có thể đặt các câu hỏi. Để đặt một câu hỏi, hãy in ra một dòng duy nhất “? $x$ $y$” ($1 \le x, y \le n$) — tọa độ của ô. Bạn sẽ nhận được câu trả lời $c$:

• Nếu $c = -1$, bạn đã đặt quá nhiều câu hỏi. Bạn nên kết thúc chương trình của mình.
• Nếu $c = 0$, ô $(x, y)$ trống.
• Nếu $c = 1$, ô $(x, y)$ bị chiếm bởi một con tàu.

Để kết thúc trò chơi, hãy in ra một dòng duy nhất “! $x$ $y$”, trong đó:

• $x = -1, y = -1$ nếu không có hình vuông $2 \times 2$ trống nào trên bảng.
• Ngược lại, $1 \le x, y \le n - 1$ và hình vuông với các ô $(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)$ là trống.

Nếu câu trả lời của bạn không chính xác, bạn sẽ nhận được một dòng với giá trị $-1$ và bạn nên kết thúc chương trình của mình. Ngược lại, bạn sẽ nhận được một dòng với giá trị $1$ và bạn nên chơi trò chơi tiếp theo (hoặc kết thúc chương trình nếu đó là trò chơi cuối cùng).

Đảm bảo rằng tổng $n$ cho tất cả các trò chơi không vượt quá $5000$.

Đảm bảo rằng bảng trong mỗi trò chơi là cố định và trình tương tác không thay đổi theo câu hỏi của bạn.

Giải pháp của bạn sẽ nhận lỗi Idleness Limit Exceeded nếu bạn không in bất cứ thứ gì hoặc quên xóa bộ đệm đầu ra (flush).

Ví dụ

Dữ liệu vào 1

2
3
0
1
4
0
1
1

Dữ liệu ra 1

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

Ghi chú

Các bảng từ ví dụ đầu tiên được hiển thị trong hình dưới đây. Các hàng tương ứng với tọa độ $x$, các cột tương ứng với tọa độ $y$.

Bảng từ trò chơi thứ nhất. Bảng từ trò chơi thứ hai.

Trong trò chơi thứ nhất, không có hình vuông $2 \times 2$ trống nào trên bảng.

Trong trò chơi thứ hai, có chính xác một hình vuông $2 \times 2$ trống trên bảng.