题目描述

$\textit{This is an interactive problem.}$

Grammy has an undirected cyclic graph of $n$ ($4 \le n \le 10^9$) vertices numbered from $1$ to $n$. An undirected cyclic graph is a graph of $n$ vertices and $n$ undirected edges that form one cycle. Specifically, there is a bidirectional edge between vertex $i$ and vertex $((i\bmod n)+1)$ for each $1 \le i \le n$.

Grammy thinks that this graph is too boring, so she secretly chooses a pair of $\textit{non-adjacent}$ vertices and connects an undirected edge (called a chord) between them, so that the graph now contains $n$ vertices and $(n+1)$ edges.

Your task is to guess the position of the chord by making no more than $40$ queries. Each query consists of two vertices $x$ and $y$, and Grammy will tell you the number of edges on the shortest path between the two vertices.

Note that the interactor is $\textit{non-adaptive}$, meaning that the position of the chord is pre-determined.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^3$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($4 \le n \le 10^9$) indicating the number of vertices.

输出格式

To ask a query, output one line. First output \texttt{?} followed by a space, then output two vertices $x$ and $y$ ($1 \le x, y \le n$) separated by a space. After flushing your output, your program should read a single integer indicating the number of edges on the shortest path between the two vertices.

To guess the position of the chord, output one line. First output $\texttt{!}$ followed by a space, then output two vertices $u$ and $v$ ($1 \le u, v \le n$) separated by a space, indicating that the chord connects vertices $u$ and $v$. After flushing your output, your program should read a single integer $r$ ($r \in \{1, -1\}$) indicating the correctness of your guess. If $r = 1$ then your guess is correct, and your program should continue processing the next test case, or exit immediately if there are no more test cases. Otherwise if $r = -1$ then your guess is incorrect, and your program should exit immediately to receive a $\texttt{Wrong Answer}$ verdict. Note that your guess does not count as a query.

To flush your output, you may use:

• $\texttt{fflush(stdout)}$ (if you use $\texttt{printf}$) or $\texttt{cout.flush()}$ (if you use $\texttt{cout}$) in C and C++.
• $\texttt{System.out.flush()}$ in Java.
• $\texttt{stdout.flush()}$ in Python.

2
6

2

1

1
4

2

1

? 1 5

? 2 4

! 4 2


? 2 4

! 1 3

提示

The graphs in the sample test cases are illustrated as follows:

:::align{center} :::