¡Ivan ha ideado nuevas reglas para el juego de batalla naval!

• El juego se jugará en un tablero de $n \times n$.
• El primer jugador elige un entero $k$ ($n \le k \le \lfloor \frac{n}{2} \rfloor^2$).
• Después de eso, el primer jugador coloca $k$ barcos en el tablero de tal manera que el número de celdas ocupadas por los barcos sea el máximo posible (entre todas las colocaciones válidas de $k$ barcos de cualquier tamaño).
• Cada barco debe ser un rectángulo de tamaño $1 \times a$ o $a \times 1$ ($a$ es cualquier entero desde $1$ hasta $n$ inclusive). Dos barcos cualesquiera no deben tener celdas vecinas (ni por lado ni por esquina).

Después de eso, el segundo jugador comienza su juego.

• El segundo jugador solo conoce el tamaño del tablero $n$.
• El segundo jugador puede realizar una consulta: ¿está la celda $(x, y)$ ocupada por algún barco?
• El segundo jugador debe encontrar cualquier cuadrado vacío de $2 \times 2$ en el tablero, o decir que no existen tales cuadrados.

El segundo jugador puede realizar como máximo $6n$ consultas. ¡Por favor, juega como el segundo jugador y gana el juego!

Protocolo de interacción

La primera línea contiene un único entero $t$ ($1 \le t \le 100$) — el número de juegos a disputar. Debes jugar $t$ juegos y finalizar la interacción después de eso.

Al comienzo del juego, se te da un único entero $n$ ($3 \le n \le 1000$) — el tamaño del tablero.

Después de eso, puedes realizar algunas consultas. Para realizar una consulta, imprime una sola línea "? $x$ $y$" ($1 \le x, y \le n$) — las coordenadas de la celda. Recibirás una respuesta $c$:

• Si $c = -1$, realizaste demasiadas consultas. Debes terminar tu programa.
• Si $c = 0$, la celda $(x, y)$ está vacía.
• Si $c = 1$, la celda $(x, y)$ está ocupada por algún barco.

Para finalizar el juego, imprime una sola línea "! $x$ $y$", donde:

• $x = -1, y = -1$ si no hay cuadrados vacíos de $2 \times 2$ en el tablero.
• De lo contrario, $1 \le x, y \le n - 1$ y el cuadrado con las celdas $(x, y)$, $(x + 1, y)$, $(x, y + 1)$, $(x + 1, y + 1)$ está vacío.

Si tu respuesta es incorrecta, recibirás una línea con el valor -1 y debes terminar tu programa. De lo contrario, recibirás una línea con el valor 1, y debes jugar el siguiente juego (o terminar tu programa si fue el último juego).

Se garantiza que la suma de $n$ para todos los juegos no excede $5000$.

Se garantiza que el tablero en cada juego es fijo y que el interactor no es adaptativo.

Tu solución obtendrá Idleness Limit Exceeded si no imprimes nada o si olvidas limpiar (flush) la salida.

Ejemplos

Entrada 1

2
3
0
1
4
0
1
1

Salida 1

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

Nota

Los tableros del primer test se muestran en las imágenes a continuación. Las filas corresponden a las coordenadas $x$, las columnas corresponden a las coordenadas $y$.

Tablero del primer juego. Tablero del segundo juego.

En el primer juego, no hay cuadrados vacíos de $2 \times 2$ en el tablero.

En el segundo juego, hay exactamente un cuadrado vacío de $2 \times 2$ en el tablero.