Mystical Swap#13122

Mystical Swap

2 seconds
256 megabytes

This is an interactive problem.

Two elements at positions and (1\le i<j\le n) have been swapped in the permutation p=(1,2,\ldots,n).

In one query, you may choose a segment [l,r] and find the number of inversions in p_l,p_{l+1},\ldots,p_r, that is, the number of index pairs such that l\le u<v\le r and p_u>p_v.

Find and using at most queries per test case. The hidden permutation is fixed before the interaction starts and does not change.

Input

First, the interactor sends one integer (1\le t\le100) — the number of test cases.

Before each test case, the interactor sends one integer (2\le n\le10^4) — the permutation length. The values and are hidden.

Output

To make a query, print a separate line ? l r, where 1\le l\le r\le n. The interactor replies with one integer — the number of inversions on this segment.

When you find the answer, print a separate line ! i j, where 1\le i<j\le n. Printing the answer does not count as a query.

After a correct answer, the interactor immediately sends for the next test case, if any. There is no additional acknowledgement. After answering the last test case, terminate your program.

After each command, print a newline and flush the output buffer, for example using cout.flush() in C++ or flush=True in Python.

An invalid command, an incorrect answer, or exceeding the query limit results in Wrong Answer. Each command must contain exactly two integer parameters. If you receive or reach the end of the input stream, terminate your program immediately.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the examples, the input column contains the interactor's messages, and the output column contains the program's commands in their execution order.

In the first example, p=(1,4,3,2,5). The interactor first sends t=1 and n=5. It replies to both ? 1 5 and ? 2 4, after which the program prints ! 2 4.

In the second example, p=(2,1). In the third example, p=(4,2,3,1): the entire segment has inversions, whereas the segment has .

Scoring

  1. Subtask ( points): n\le4.

  2. Subtask ( points): n\le15.

  3. Subtask ( points): i=1.

  4. Subtask ( points): no additional constraints.