F. Where the West Wind Ends
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

After Anaxagoras stated that his objective is complete, he went to meet Castorice in the nether realm. He then taught her his last lesson — the range LIS query algorithm, before he passed away. As a reminder, an LIS of a sequence is a subsequence$$$^{\text{∗}}$$$ such that its elements are strictly ascending with the largest length. Castorice is very intrigued by the algorithm, and she wants to test her implementation with your help.

Specifically, she has an array $$$a$$$ of length $$$n$$$, which contains integers from $$$1$$$ to $$$3$$$. It is also guaranteed that the array contains at least one occurrence of each integer from $$$1$$$ to $$$3$$$. You can ask her a query $$$(l,r)$$$, and she gives you the length of LIS of $$$[a_l, a_{l+1}, \dots, a_r]$$$. Your task is to determine an index $$$i$$$ and a value $$$x$$$ such that $$$a_i$$$ is NOT equal to $$$x$$$.

However, since Castorice is in the nether realm, you must communicate with her through Mydei, who has limited patience. He only allows you to ask no more than $$$20$$$ queries before he gets annoyed. Can you finish your task under such constraints?

$$$^{\text{∗}}$$$A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

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 one integer $$$n$$$ ($$$3 \le n \le 10^5$$$).

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

Interaction

To make a query, output a line in the following format (do not include quotes):

"$$$\mathtt{?}$$$ $$$l$$$ $$$r$$$" ($$$1\le l \le r \le n$$$)

Here, $$$l$$$ and $$$r$$$ represent the left and right bounds of your query.

After each query, you should read a line containing one integer, indicating the length of LIS of $$$[a_l, a_{l+1}, \dots, a_r]$$$.

When you are ready to print the answer, output a single line in the following format:

"$$$\mathtt{!}$$$ $$$i$$$ $$$x$$$" ($$$1 \le i \le n$$$, $$$1 \le x \le 3$$$)

Here, $$$i$$$ represents your answer index, and $$$x$$$ represents the value that $$$a_i$$$ is not equal to.

You can make at most $$$20$$$ queries in each test case.

The interactor is NOT adaptive, meaning that the answer is known before the participant asks the queries and doesn't depend on the queries asked by the participant.

If your program makes more than $$$20$$$ queries for one test case, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you may get Idleness limit exceeded verdict. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • Console.Out.Flush() in C#;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
1
6

3

2
Output


? 1 4

? 3 6

! 3 1
Note

In the example, the array is $$$[1,1,2,3,1,3]$$$.

The first query asks the length of LIS of $$$[1,1,2,3]$$$, which is $$$3$$$.

The second query asks the length of LIS of $$$[2,3,1,3]$$$, which is $$$2$$$.