Guess the number

This is an interactive problem. Please read the entire statement carefully to understand how to handle such problems.

The jury has selected an integer between $1$ and $n$, and your task is to guess it. You can inquire about any number from $1$ to $n$, and the jury will respond with "1" if this number is greater than or equal to the chosen number, or "0" otherwise.

Input

The first line contains two integers $t$ and $q$ ($1\le t\le 100$) — the number of test cases and the maximum number of queries allowed for each test. The constraint on $q$ is detailed below.

Interaction

For each test case, you will first receive an integer $n$ ($1\le n\le 1,000$) — the upper limit of the possible number.

To make a query, output "1 $v$" ($1\le v\le n$).

In response to your query, the jury program will return "1" if $v$ is greater than or equal to the chosen number, otherwise "0".

After making a query, ensure you output a newline character and flush the output buffer. To flush the buffer, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• stdout.flush() in Python;

Refer to the documentation for other languages.

If your query is invalid (exceeding the query limit or not adhering to constraints), the interactor will output "-1" and terminate. If you receive "-1", immediately terminate your program to avoid an arbitrary verdict and receive a "Wrong Answer" verdict instead.

Once you determine the answer $a$, output "2 $a$". This does not count towards the $q$ queries you are allowed.

After solving the last test case, you must terminate your program; otherwise, proceed to the next test case.

Templates for C++, Java, Python, and Pascal are available and can be utilized.

Examples

2 10
10

0

1

8

1

1

0

1 2

1 3

2 3

1 8

1 7

1 6

2 7

Scoring

$q$ — the maximum number of queries your program can use.

1. ($40$ points) $q=1,000$;

2. ($59$ points) $q=15$;

3. ($1$ point) $q=10$.