Area 51

Limits 1s, 512 MB · Interactive

Toky and Efa are playing an interesting game. A brief description of the game is given below.

Suppose $h$, $w$ and $a$ are the height, width and area of a rectangle respectively. So ${a = h * w}$. Efa has kept the area secret and Toky has to find it by guessing height and width. Don't worry, Efa also gives the maximum possible value of $h$ and $w$. That means, Efa gives Toky an integer $n$ and he has to guess two integers $h$ and $w$ between $1$ and $n$ ${(1 \le h, w \le n)}$ such that ${h * w = a}$. But Toky doesn’t have much time to finish the game because he wants to participate in Code To Save A Mother and Toky also doesn’t want to make Efa sad. So, he wants you to play with her as you are the only one here without them.

Now, here is the interesting part. You don’t have to find the area by one chance. In reply of your guessing, Efa will tell your guessed area is equal or less or greater than the hidden area. But she doesn’t like to talk much. So, she will reply your guess not more than $20$ times. Can you find out the area?

Input

The first line of the input is an integer, $t$ ${(1 \le t \le 1000)}$ denoting the number of test cases means how many times Efa wants to play.

Each test case has an integer, $n$ ${(1 \le n \le 1000)}$ denoting the maximum possible value of ${h, w}$.

You have to start guessing after receiving $n$. To inform your guess, you have to print in the following way (without quotes).

“$?$ $h$ $w$”

After printing, you will have to read one character based on the following incidents.

• If ${h * w > a}$, you will receive a character “$>$” (without quotes)

• If ${h * w < a}$, you will receive a character “$<$“ (without quotes)

• If ${h * w = a}$, you will receive a character “$=$” (without quotes). After receiving this, you have to print "$= a$" (without quotes) and exit from current test case immediately.

• If you try to guess more than $20$ times or after receiving “$=$” or print invalid characters (any character without $?$ and $=$), invalid numbers (non-positive or ${h > n}$ or ${w > n}$), you will receive a character “$!$” (without quotes) and you must terminate your program after receiving this. If you terminate, you will receive Wrong Answer otherwise you will get any arbitrary non-accepted verdict.

This is an interactive problem. So, You have to flush output after printing each line. In C++, you should use endl or fflush(stdout) after printing each line. For other languages, see the language documentation.

Output

Let, $t = 1$ and $n = 6$, here is a sample interaction for $a = 16$.

I: 1
I: 6
O: ? 1 2
I: <
O: ? 5 6
I: >
O: ? 4 4
I: =
O: = 16