Ceci est un problème interactif.

Ivan a inventé de nouvelles règles pour le jeu de bataille navale !

• Le jeu se joue sur une grille de taille $n \times n$.
• Le premier joueur choisit un entier $k$ ($n \le k \le \lfloor \frac{n}{2} \rfloor^2$).
• Ensuite, le premier joueur place $k$ navires sur la grille de telle sorte que le nombre de cases occupées par les navires soit le maximum possible (parmi tous les placements valides de $k$ navires de tailles quelconques).
• Chaque navire doit être un rectangle de taille $1 \times a$ ou $a \times 1$ ($a$ est un entier compris entre $1$ et $n$ inclus). Deux navires ne doivent pas avoir de cases adjacentes (ni par les côtés, ni par les coins).

Après cela, le second joueur commence sa partie.

• Le second joueur connaît uniquement la taille de la grille $n$.
• Le second joueur peut poser une question : la case $(x, y)$ est-elle occupée par un navire ?
• Le second joueur doit trouver un carré $2 \times 2$ vide sur la grille, ou indiquer qu'il n'existe aucun carré de ce type.

Le second joueur peut poser au maximum $6n$ questions. Veuillez jouer en tant que second joueur et gagner la partie !

Interaction

La première ligne contient un entier unique $t$ ($1 \le t \le 100$) — le nombre de parties à jouer. Vous devez jouer $t$ parties et terminer l'interaction après cela.

Au début de chaque partie, vous recevez un entier unique $n$ ($3 \le n \le 1000$) — la taille de la grille.

Ensuite, vous pouvez poser des questions. Pour poser une question, affichez une seule ligne « ? $x$ $y$ » ($1 \le x, y \le n$) — les coordonnées de la case. Vous recevrez une réponse $c$ :

• Si $c = -1$, vous avez posé trop de questions. Vous devez terminer votre programme.
• Si $c = 0$, la case $(x, y)$ est vide.
• Si $c = 1$, la case $(x, y)$ est occupée par un navire.

Pour terminer la partie, affichez une seule ligne « ! $x$ $y$ », où :

• $x = -1, y = -1$ s'il n'y a aucun carré $2 \times 2$ vide sur la grille.
• Sinon, $1 \le x, y \le n - 1$ et le carré formé par les cases $(x, y)$, $(x + 1, y)$, $(x, y + 1)$, $(x + 1, y + 1)$ est vide.

Si votre réponse est incorrecte, vous recevrez une ligne avec la valeur -1, et vous devez terminer votre programme. Sinon, vous recevrez une ligne avec la valeur 1, et vous devrez jouer la partie suivante (ou terminer votre programme si c'était la dernière partie).

Il est garanti que la somme des $n$ pour toutes les parties ne dépasse pas $5000$.

Il est garanti que la grille dans chaque partie est fixe et que l'interacteur n'est pas adaptatif.

Votre solution recevra une erreur Idleness Limit Exceeded si vous n'affichez rien ou si vous oubliez de vider le tampon de sortie (flush).

Exemples

Entrée 1

2
3
0
1
4
0
1
1

Sortie 1

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

Remarque

Les grilles du premier test sont illustrées ci-dessous. Les lignes correspondent aux coordonnées $x$, les colonnes correspondent aux coordonnées $y$.

Grille de la première partie. Grille de la deuxième partie.

Dans la première partie, il n'y a aucun carré $2 \times 2$ vide sur la grille.

Dans la deuxième partie, il y a exactement un carré $2 \times 2$ vide sur la grille.