Problem Statement

This is an interactive problem (where your program interacts with the judge system via Standard Input and Output).

You are given a positive integer $N$.

For a set $X$ of positive integers, a subset of $X$ whose sum is $N$ is called a special subset of $X$.

The judge system has a hidden set $A$ that satisfies all of the following conditions, but you cannot directly know the values of the elements of $A$.

• $|A|=\left\lfloor\frac{N}{2}\right\rfloor$
• Every element of $A$ is an integer between $1$ and $N-1$, inclusive.

You may ask the judge system the following question at most $\left\lfloor\frac{3N}{4}\right\rfloor$ times.

• Choose an integer $a$ between $1$ and $N-1$, inclusive, and ask whether $a$ is contained in $A$.

Determine whether the hidden set $A$ has a special subset, and if it does, find the minimum number of elements in a special subset.

Solve $T$ test cases for each input.

Constraints

• $1 \leq T \leq 5 \times 10^4$
• $4 \leq N \leq 2 \times 10^5$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Interaction

This is an interactive problem (where your program interacts with the judge system via Standard Input and Output).

First, receive the number of test cases $T$ from Standard Input.

T

Then, $T$ test cases follow. Each test case proceeds as follows.

Receive the integer $N$ from Standard Input.

N

Then, you may ask at most $\left\lfloor\frac{3N}{4}\right\rfloor$ questions. Print each question to Standard Output in the following format:

? a

Here, $a$ must satisfy the following:

• $1 \leq a \leq N-1$
• $a$ is an integer.

In response, Yes is given from Standard Input if $a$ is contained in $A$, and No is given otherwise.

However, if $a$ does not satisfy the conditions above, or if the number of questions exceeds $\left\lfloor\frac{3N}{4}\right\rfloor$, -1 is returned.

If the judge returns -1, your program is already considered incorrect. In this case, terminate your program immediately.

Let $S=-1$ if $A$ has no special subset; otherwise, let $S$ be the minimum number of elements in a special subset. Once you have found $S$, print it to Standard Output in the following format.

! S

Then, proceed to the next test case if one exists. After processing the last test case, terminate your program immediately.

Note

• For each output, add a newline at the end and flush Standard Output. Otherwise, you may receive a TLE verdict.
• If your program prints output in an incorrect format during the interaction or terminates prematurely, the verdict is indeterminate.
• After processing the last test case, terminate your program immediately. Otherwise, the verdict is indeterminate.
• The judge of this problem is not adaptive. The judge fixes the set $A$ for every test case before the interaction.

Sample Interaction

The following is a sample interaction for $N=6,A=\lbrace1,2,4\rbrace$. In this case, $\left\lfloor\frac{3N}{4}\right\rfloor=4$, so you may ask at most $4$ questions.