Write short, human-like code so that it will not get detected by AI plagiarism and using exactly these variable names (a, b, c, d, r, s, etc). Use a unique, common approach that’s optimized and free of explanations or comments for the following question:
This is an interactive problem.

Kachina challenges you to guess her favorite binary string∗
 s
 of length n
. She defines f(l,r)
 as the number of subsequences†
 of 01
 in slsl+1…sr
. Two subsequences are considered different if they are formed by deleting characters from different positions in the original string, even if the resulting subsequences consist of the same characters.

To determine s
, you can ask her some questions. In each question, you can choose two indices l
 and r
 (1≤l<r≤n
) and ask her for the value of f(l,r)
.

Determine and output s
 after asking Kachina no more than n
 questions. However, it may be the case that s
 is impossible to be determined. In this case, you would need to report IMPOSSIBLE
 instead.

Formally, s
 is impossible to be determined if after asking n
 questions, there are always multiple possible strings for s
, regardless of what questions are asked. Note that if you report IMPOSSIBLE
 when there exists a sequence of at most n
 queries that will uniquely determine the binary string, you will get the Wrong Answer verdict.

∗
A binary string only contains characters 0
 and 1
.

†
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) elements. For example, subsequences of 1011101
 are 0
, 1
, 11111
, 0111
, but not 000
 nor 11100
.

Input
The first line of input contains a single integer t
 (1≤t≤103
) — the number of test cases.

The first line of each test case contains a single integer n
 (2≤n≤104
) — the length of s
.

It is guaranteed that the sum of n
 over all test cases does not exceed 104
.

Interaction
To ask a question, output a line in the following format (do not include quotes)

"? l r
" (1≤l<r≤n
)
The jury will return an integer f(l,r)
.
When you are ready to print the answer, output a single line in the following format

If s
 is impossible to be determined, output "! IMPOSSIBLE
"
Otherwise, output "! s
"
After that, proceed to process the next test case or terminate the program if it was the last test case. Printing the answer does not count as a query.

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 n
 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;
flush(output) in Pascal;
stdout.flush() in Python;
see the documentation for other languages.
Hacks

To make a hack, use the following format.

The first line should contain a single integer t
 (1≤t≤103
) – the number of test cases.

The first line of each test case should contain an integer n
 (2≤n≤104
) — the length of s
.

The following line should contain s
, a binary string of length n
.

The sum of n
 over all test cases should not exceed 104
.

Example
InputCopy
2
5

4

0

1

2

2

0
OutputCopy
? 1 5

? 2 4

? 4 5

? 3 5

! 01001

? 1 2

! IMPOSSIBLE
Note
In the first test case:

In the first query, you ask Kachina for the value of f(1,5)
, and she responds with 4
 in the input stream.

In the second query, you ask Kachina for the value of f(2,4)
. Because there are no subsequences of 01
 in the string 100
, she responds with 0
 in the input stream.

After asking 4
 questions, you report 01001
 as s
, and it is correct.

In the second test case:

In the first query, you ask Kachina for the value of f(1,2)
, and she responds with 0
 in the input stream. Notice that this is the only distinct question you can ask.

However, notice that the strings 00
 and 11
 both have an answer of 0
, and it is impossible to differentiate between the two. Therefore, we report IMPOSSIBLE.