Determine the Hair Dye Threshold

Linda loves periodically changing her hair color; when her boyfriend Archie notices the change, Linda becomes very happy. Archie comments on Linda’s new hair color if and only if he notices that Linda’s hair color has changed. This guarantees that Linda always knows whether Archie has detected the change.

Now, there is a new series of hair dyes available on the market with N colors numbered from 1 to N. The similarity between two colors is determined by the difference in their numbers; the smaller the difference, the more similar the colors are.

Linda has observed that for this series there is a color-difference threshold \(C\) (\(1 \le C \le N\)). Specifically, if Linda previously used dye color color_prev and now intends to use dye color color_new, then Archie will notice the change if and only if \(|color_{new} - color_{prev}| \ge C\).

Linda has purchased one set of these dyes and will conduct an experiment by repeatedly changing her hair color. Note that since each dye can only be used once, every color can be chosen at most once.

Before the experiment, Linda’s hair was colored with a dye from another series, so the reaction to her first dye change is not considered.

Linda now wishes to determine the threshold \(C\) in the limited time she has. Help her accomplish this task.

Interaction

This is an interactive problem. Note: In order to reduce the number of test cases, a single test file contains multiple test cases.

The first line of input contains an integer \(T\), the number of test cases. For each test case, you are first given an integer \(N\), the number of hair dye colors available.

You may then issue queries of the form ? P (without quotes), where \(P\) is the dye color Linda will use next (\(1 \le P \le N\)). All queries must use distinct values of \(P\).

After each query, your program will receive an integer: 1 if Archie noticed the change in hair color, and 0 otherwise. Remember that the first dye change is not counted since it is from a different series.

When you have determined the threshold \(C\), output your answer as = C (without quotes). If your answer is correct, the interaction will continue with the next test case; otherwise, your program will terminate immediately.

You are allowed at most 64 queries per test case (the final answer does not count as a query). Make sure to flush the output buffer after every output line.

inputFormat

The input begins with an integer \(T\), the number of test cases. For each test case, an integer \(N\) is provided on one line, followed by a hidden threshold value \(C\) (this value simulates the behavior of the interactive judge in offline testing). In actual interactive testing, the threshold \(C\) is not provided to your solution.

Note for offline simulation: The test input will be in the format below:

T
N1 C1
N2 C2
... 
NT CT

outputFormat

For each test case, output a single line of the form = C where \(C\) is the determined threshold. Each answer must be printed on a separate line.

sample

3
10 3
5 1
8 8

= 3
= 1
= 8

</p>