Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Area 51

By rifatrraazz · Limits 1s, 512 MB · Interactive

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

Suppose hh, ww and aa are the height, width and area of a rectangle respectively. So a=hw{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 hh and ww. That means, Efa gives Toky an integer nn and he has to guess two integers hh and ww between 11 and nn (1h,wn){(1 \le h, w \le n)} such that hw=a{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 2020 times. Can you find out the area?

Input

The first line of the input is an integer, tt (1t1000){(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, nn (1n1000){(1 \le n \le 1000)} denoting the maximum possible value of h,w{h, w}.

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

?? hh ww

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

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

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

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

  • If you try to guess more than 2020 times or after receiving “==” or print invalid characters (any character without ?? and ==), invalid numbers (non-positive or h>n{h > n} or w>n{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=1t = 1 and n=6n = 6, here is a sample interaction for a=16a = 16.

1
6
? 1 2
<
? 5 6
>
? 4 4
=
= 16

    Discussion

    Statistics


    25% Solution Ratio

    YouKnowWhoEarliest, 2M ago

    Deshi_TouristFastest, 0.1s

    Deshi_TouristLightest, 4.2 MB

    Tahmid690Shortest, 1024B

    Submit

    Login to submit

    Related Contests