Do you know what tubular bells are? They are a musical instrument made up of cylindrical metal tubes. In an orchestra, tubular bells are used to mimic the ringing of bells.
Mike has tubular bells, too! They consist oftubes, and each of the tubes has a length that can be expressed by a integer from to inclusive. It is clear that the lengths of all the tubes are different (it makes no sense to make the same tubes). It is also known that .
Formally, we can say that Mike’s tubular bells are described by a permutationof length that contains all numbers from to inclusive, with denoting the length of the -th tube.
You are offered an interesting task: to guess what Mike’s instrument looks like. Simply, you must guess the permutation.
Mike won’t tell youor . He will only tell you , and will allow you to ask no more than queries.
In each query, you name two positive integers, such that . In response to this query, the program written by Mike will give you , where denotes the least common multiple of and .
Solve Mike’s problem!
Each test contains multiple test cases.
The first line contains one positive integer( ), denoting the number of test cases. Description of the test cases follows.
The single line of each test case contains one positive integer( ) — number of tubes in Mike’s tubular bells. Also , i.e. the lengths of the tubes do not exceed .
It is guaranteed that the sum of maximal number of queries (i.e. ) over all test cases does not exceed . It means that sum of does not exceed .
For each set of input data, read one integer. You are allowed to make no more than queries.
If you want to make a query, output it in the format “?“, where and — the numbers of tubes for which you learn the lcm (least common multiple) of their lengths. Note that must be satisfied. The interactor will return a single integer —the answer to your query.
If you are ready to print the answer, print it in the format “! The output of the answer is not considered a query and is not included in the number of queries.… “.
After each query and answer output, don’t forget to output the line translation and reset the output buffer. Otherwise you will get the verdict “Idleness limit exceeded”. To reset the buffer use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.
Note that the interactor is not adaptive. That is, the original permutation is fixed in the beginning and don’t depend on your queries.
Use the following format for hacks:
The first line contains a single positive integer( ) — the number of input datasets. A description of the input data sets is given below.
The first line of each test case contains one positive integer( ) —the number of tubes. It is known that , i.e. the lengths of the tubes do not exceed .
The second line of each test case contains an arrayof positive integers — the lengths of the tubes in each input dataset. Remember that and , and that all are different.
3 5 8 10 7 6 9 5 24 25 28 27 26 7 1 2 3 4 5 6 7
? 1 2 40 ? 2 5 90 ? 3 1 56 ? 4 5 18 ! 8 10 7 6 9 ? 1 5 312 ? 2 4 675 ! 24 25 28 27 26 ? 1 4 4 ? 2 5 10 ? 3 7 21 ? 6 2 6 ? 2 5 10 ? 1 2 2 ? 1 2 2 ? 1 2 2 ? 1 2 2 ? 1 2 2 ! 1 2 3 4 5 6 7