Background

“Is Double Star hard? I rks12.66.”

As everyone knows, Phigros needs chart delay calibration. In a far, yet maybe not so far future, Cruxkarl-chan invented a machine that can automatically play Phigros, but she actually forgot what chart delay was set on the machine.

As a result, she got the “great” achievement of all Bad, got angry, and left the lab. You came to the lab and saw the machine in a total mess. To help Cruxkarl-chan, you decide to secretly measure the machine’s chart delay.

Problem Description

This is an interactive problem.

The interactive library has an integer $x\in [-400,600]$. Each time, you can query an integer $y\in [-1000,1000]$, and then the library returns an answer based on the following cases:

1. Perfect: $|x-y|\in [0,80]$.
2. Good: $|x-y|\in (80,160]$.
3. Bad: $|x-y|\in (160,180]$.
4. Miss: $|x-y|\in (180,\infty)$.

You need to output the correct result $x$ within $10$ queries.

Interaction Method

This problem has multiple testdata.

The first line contains the number of test cases $T (1\le T\le 1000)$.

For each test case:

When you need to make a query:

• Output in the format ? y and flush the output buffer. You must ensure $-1000\le y\le 1000$, and the current number of queries (including this one) does not exceed $10$. Otherwise, the interactive library may encounter an unknown error.

• Then, read a string $s$ representing the returned message.

When you have obtained the answer, output in the format ! x and flush the output buffer.

After processing all test cases, terminate the program immediately.

1

Perfect

Good

Miss

? 0

? 100

? 200

! 0

Hint

When the answer is $0$, the results of querying $0,100,200$ are as shown in the sample.

How to flush the output buffer:

• In C and C++, use fflush(stdout) (if you use $\text{printf}$) or cout.flush() (if you use $\text{cout}$).
• In Python, use stdout.flush().
• In particular, in C++, using cout<<endl will automatically flush the buffer.

If you still have questions about interactive problems, a sample code is shown below:

#include<stdio.h>
#include<string.h>
#include<iostream>
int main(){
	int t; cin>>t;
    while(t--){
        cout<<"? "<<0<<endl;
        string s;cin>>s;
        printf("0\n"); fflush(stdout);
    }
	return 0;
}

If you have nothing to do, you can try to solve this problem within $9$ queries.

Translated by ChatGPT 5