44pts（我估计是task1 10 task2 20 task3/4 7）

思路：倍增

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;
inline ll read(){
	char c=getchar();ll ans=0;
	while(c<'0'||c>'9'){
		if(c=='-')exit(0);
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans;
}
ll t,rd,trd,i,x,y;
signed main(){
	t=read();
	while(t--){
		cout<<"? 0"<<endl;
		rd=read();
		if(rd==1){
			x=0,i=1;
			do{
				cout<<"? "<<i<<endl;
				rd=read();
				if(i<<1<=1000000000)i<<=1;
			}while(rd);
			y=i>>1,x=i>>2;
			if(i>>3){
			i=i>>3;
			while(1){
				cout<<"? "<<x+i<<endl;
				rd=read();
				if(rd)x+=i;
				if(i>>1)i>>=1;
				else break;
			}
			}
			i=1;
			do{
				cout<<"? "<<y+i<<endl;
				rd=read();
				if(i<<1<=1000000000)i<<=1;
			}while(!rd);
			y+=i>>2;
			if(i>>3){
			i>>=3;
			while(1){
				cout<<"? "<<y+i<<endl;
				rd=read();
				if(!rd)y+=i;
				if(i>>1)i>>=1;
				else break;
			}
			}
			cout<<"! "<<(y-x)*(y-x)+y-2*x<<endl;
		}else{
			y=0,i=1;
			do{
				cout<<"? "<<i<<endl;
				rd=read();
				if(i<<1<=1000000000)i<<=1;
			}while(!rd);
			x=i>>1,y=i>>2;
			if(i>>3){
			i>>=3;
			while(1){
				cout<<"? "<<y+i<<endl;
				rd=read();
				if(!rd)y+=i;
				if(i>>1)i>>=1;
				else break;
			}
			}
			i=1;
			do{
				cout<<"? "<<x+i<<endl;
				rd=read();
				if(i<<1<=1000000000)i<<=1;
			}while(rd);
			x+=i>>2;
			if(i>>3){
			i>>=3;
			while(1){
				cout<<"? "<<x+i<<endl;
				rd=read();
				if(rd)x+=i;
				if(i>>1)i>>=1;
				else break;
			}
			}
			cout<<"! "<<(x-y-1)*(x-y-1)-y-1<<endl;
		}
	}
	return 0;
}