Background

I do not really know why I want to tell this story. I also do not quite understand what clowns have to do with chefs, but since at this moment they are arranged on my draft paper (see the attached picture), I can only try to talk about it.

Uh, you are right. I really cannot think of any relationship between them.

Well, the clown appears here probably mostly because he always shows up with something strange.

But I still think the role of a chef is interesting.

But, but, what does this have to do with "hibernal" ?

Ah, let us talk about the chef instead. Ingredients are still interesting.

Hey, actually vegetables can provide a much richer texture than meat, but it seems everyone disagrees with my view. What about you?

Add a space between English letters and Chinese characters. Let me check.

[AI drawing] girl, naked back, neck fetish.

Ah, I got it. This seems like it could be an interesting story. Hmm, writing it might take a lot of time, so you should pass this problem first and then come urge me qwq.

Should I say something at the end to be polite? Then I wish everyone good health. Yay!

Problem Description

There are $n$ apples. The $i$-th apple is labeled $i$. Exactly $2$ of them are golden apples.

In each query, you can divide the $n$ apples into two sets $S_1, S_2$, and each apple must belong to exactly one set.

Let $x$ be the number of golden apples in $S_1$, and $y$ be the number of golden apples in $S_2$. The interactive judge will return the value of $x \times y$.

Please find the labels of the two golden apples within at most $19$ queries.

The interactive judge is adaptive, meaning the labels of the two golden apples may change as queries are made, but they will always satisfy all queries that have already happened (see the sample).

Input Format

This problem has multiple test cases. The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain a positive integer $n$, the number of apples in this test case.

This problem uses interactive I/O.

Interaction Format

• ? k a1 a2 a3 ... ak Put these $k$ apples into one set, and put the other $n-k$ apples into the other set. The interactive judge will return an integer $x$ as the answer. You must ensure $0<k<n$.
• ! x y Output the answer. You must ensure $x<y$.

Note: In each test case, the total number of the first type of operations must not exceed $19$.

Also note that after each operation, you need to call the following function to flush the output buffer:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);

For other languages, please check the corresponding documentation.

Output Format

See "Interaction Format".

1
5

1

0

? 3 1 2 3

? 2 2 4

! 1 5

Hint

The sample is only for understanding the interaction process and may not be logically consistent.

[Sample Explanation]

Initially, the two golden apples are $3,5$.

In the first query, each set has $1$ golden apple, so the judge returns $1$, and the labels of the golden apples do not change.

In the second query, one set has $2$ golden apples and the other set has none, so the judge returns $0$. Then the two golden apples change from $3,5$ to $1,5$. It is easy to see that although the labels of the golden apples changed, the answers to the first two queries are still satisfied.

You answer $1,5$, the answer is correct, and the interaction ends.

Constraints

Scoring

For each testdata, among the $200$ test cases, take the one with the maximum number of queries. If it exceeds $19$ queries, the score is $0$. Otherwise, you get full score.

The interactive judge is guaranteed to run within 0.1 s under normal conditions.

If your output is invalid, TLE/WA and other results may occur.

Translated by ChatGPT 5