Guess the String
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2600
Tags: constructive algorithms, interactive, probabilities

This is an interactive problem. You have to use flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java or Kotlin — System.out.flush(), and in Python — sys.stdout.flush().

The jury has a string $$$s$$$ consisting of characters 0 and/or 1. The first character of this string is 0. The length of this string is $$$n$$$. You have to guess this string. Let's denote $$$s[l..r]$$$ as the substring of $$$s$$$ from $$$l$$$ to $$$r$$$ (i. e. $$$s[l..r]$$$ is the string $$$s_ls_{l+1} \dots s_r$$$).

Let the prefix function of the string $$$s$$$ be an array $$$[p_1, p_2, \dots, p_n]$$$, where $$$p_i$$$ is the greatest integer $$$j \in [0, i-1]$$$ such that $$$s[1..j] = s[i-j+1..i]$$$. Also, let the antiprefix function of the string $$$s$$$ be an array $$$[q_1, q_2, \dots, q_n]$$$, where $$$q_i$$$ is the greatest integer $$$j \in [0, i-1]$$$ such that $$$s[1..j]$$$ differs from $$$s[i-j+1..i]$$$ in every position.

For example, for the string 011001, its prefix function is $$$[0, 0, 0, 1, 1, 2]$$$, and its antiprefix function is $$$[0, 1, 1, 2, 3, 4]$$$.

You can ask queries of two types to guess the string $$$s$$$:

- $$$1$$$ $$$i$$$ — "what is the value of $$$p_i$$$?";
- $$$2$$$ $$$i$$$ — "what is the value of $$$q_i$$$?".

You have to guess the string by asking no more than $$$789$$$ queries. Note that giving the answer does not count as a query.

In every test and in every test case, the string $$$s$$$ is fixed beforehand.

Interaction format:
Initially, the jury program sends one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

At the start of each test case, the jury program sends one integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the length of the string.

After that, your program can submit queries to the jury program by printing one of the following lines (do not forget to flush the output after printing a line!):

- $$$1$$$ $$$i$$$ — the query "what is the value of $$$p_i$$$?";
- $$$2$$$ $$$i$$$ — the query "what is the value of $$$q_i$$$?".

For every query, the jury prints one integer on a separate line. It is either:

- the answer for your query, if the query is correct and you haven't exceeded the query limit;
- or the integer $$$-1$$$, if your query is incorrect (for example, the constraint $$$1 \le i \le n$$$ is not met) or if you have asked too many queries while processing the current test case.

To submit the answer, your program should send a line in the following format (do not forget to flush the output after printing a line!):

- $$$0$$$ $$$s$$$, where $$$s$$$ is a sequence of $$$n$$$ characters 0 and/or 1.

If your guess is correct, the jury program will print one integer $$$1$$$ on a separate line, indicating that you may proceed to the next test case (or terminate the program, if it was the last test case) and that the number of queries you have asked is reset. If it is not correct, the jury program will print one integer $$$-1$$$ on a separate line.

After your program receives $$$-1$$$ as the answer, it should immediately terminate. This will lead to your submission receiving the verdict "Wrong Answer". If your program does not terminate, the verdict of your submission is undefined.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
The example contains one possible way of interaction in a test where $$$t = 2$$$, and the strings guessed by the jury are 011001 and 00111. Note that everything after the // sign is a comment that explains which line means what in the interaction. The jury program won't print these comments in the actual problem, and you shouldn't print them. The empty lines are also added for your convenience, the jury program won't print them, and your solution should not print any empty lines.

Example input:
2 // 2 test cases
6 // n = 6

0 // p[3] = 0

1 // q[2] = 1

4 // q[6] = 4

1 // p[4] = 1

1 // answer is correct
5 // n = 5

1 // p[2] = 1

2 // q[4] = 2

2 // q[5] = 2

1 // answer is correct

Example output:
1 3      // what is p[3]?

2 2      // what is q[2]?

2 6      // what is q[6]?

1 4      // what is p[4]?

0 011001 // the guess is 011001


1 2      // what is p[2]?

2 4      // what is q[4]?

2 5      // what is q[5]?

0 00111  // the guess is 00111

Editorial:
We will design a randomized solution which spends $$$1.5$$$ queries on average to guess $$$2$$$ characters.
First of all, let's ask $$$p_2$$$ to learn which character is $$$s_2$$$. Depending on whether it is 0 or 1, the details of the solution might change, but the general idea stays the same. We will assume that it is 0.
We will divide the string into blocks of $$$2$$$ characters and guess it block by block. Suppose a block contains the characters $$$s_{i - 1}$$$ and $$$s_i$$$. If we want to guess it using less than $$$2$$$ queries, we should start with querying the $$$i$$$-th position (if we start by querying the position $$$i-1$$$, we won't know anything about the $$$i$$$-th position).
Suppose our query has returned a number greater than $$$1$$$. Then we successfully obtained the full information about the block in one query. So, let's analyze the bad case: what if we got $$$0$$$ or $$$1$$$ as the result of the query?
If we used prefix function, the result equal to $$$1$$$ shows us that the block is 10 — 00 will give the result of at least $$$2$$$, and neither 01 nor 11 can give $$$1$$$ as the result. But if the result is $$$0$$$, then it could mean either 01 or 11, and we need a second query to find out the exact combination.
If we used antiprefix function, every character gets inverted; so, the result equal to $$$1$$$ tells us that the block is 01, and the result equal to $$$0$$$ tells us that the block is either 10 or 00.
So, one type of query cannot distinguish 01 from 11, and the other type cannot distinguish 10 from 00. If we pick the type of query randomly, with probability of $$$\frac{1}{2}$$$ we will obtain the information about the whole block in just one query; so, this method will spend $$$1.5$$$ queries per block of $$$2$$$ characters on average.