J. Someone's Favourite Problem
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden directed graph $$$G$$$ consisting of $$$n$$$ vertices. It is guaranteed that $$$G$$$ does not contain self loops or multiple edges. Your task is to determine whether $$$G$$$ contains a vertex with in-degree $$$n-1$$$ and out-degree $$$0$$$.

You may ask queries of the following format:

  • ? u v: does there exist an edge from vertex $$$u$$$ to $$$v$$$?

Please find any vertex that satisfies the above conditions, or determine that such a vertex does not exist, using no more than $$$3n$$$ queries.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^3$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Interaction

To ask a query, print a line in the following format:

  • ? u v: does there exist an edge from vertex $$$u$$$ to $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$)?

The judge will respond with an integer $$$x$$$. If $$$x=1$$$, there is an edge from vertex $$$u$$$ to $$$v$$$; if $$$x=0$$$, there is no edge from vertex $$$u$$$ to $$$v$$$.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

To report the answer, print a line in the following format:

  • ! y: if there exists such a vertex, $$$y$$$ ($$$1 \le y \le n$$$) represents its label. Otherwise, $$$y=-1$$$.

After that, proceed to process the next test case or terminate the program if it was the last test case.

Note that reporting the answer does not count towards the number of queries.

Note that the interactor is adaptive. This means that $$$G$$$ may change during the interaction, but it is guaranteed that there is always some graph that satisfies the answers to all previous queries.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2
4

1

0

4

0

1
Output


? 1 2

? 3 1

! 2

? 1 4

? 4 3

! -1
Note

The two graphs in the sample test are given below: