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 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 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 ? 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 ! 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 Wrong Answer verdict. Note that your guess does not count as a query.
To flush your output, you may use:
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:
