问两个相乘不会炸 \(\rm long \ long\) 的质数，用 CRT 合并，得到 \(\frac{p}{q} \equiv r \ \pmod M\)。其中 \(M\) 是大于 \(10^{18}\) 的数。
由于这个 \(M\) 太大了，不存在 \(\frac{p}{q} \equiv \frac{a}{b} \pmod M\) 且 \(p,q,a,b \leq 10^9\)，所以我们只需找到一个 \(\frac{p}{q}\) 满足条件。
稍微转化一下条件变成找到一个 \(q \leq 10^9\) 使 \(qr \leq 10^9 \pmod M\)。改写式子成 \(qr = kM + x \Rightarrow \frac{r}{M} = \frac{k}{q} + \frac{x}{M}\)。由于这个 \(x \leq 10^9\)，\(\frac{x}{M}\) 很小，忽略不计，那么 \(\frac{r}{m}\) 近似于 \(\frac{k}{q}\)。但是在模意义下这个近似不一定满足条件，所以要将所有近似 \(\frac{r}{m}\) 的 \(\frac{k}{q}\) 都试一遍。在 S-B Tree 上二分即可。
由于朴素的二分速度过慢，可以用倍增跳过几个点，选若干点判定。这样可能会漏，多选几个询问的质数，可以卡过去。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
typedef __int128_t i128;
inline ll qmul(ll a,ll b,const ll &mod){return (i128)a*b%mod;}
inline ll ksm(ll b,ll p,const ll &mod){ll ret=1;while(p){if(p&1)ret=ret*b%mod;b=b*b%mod;p>>=1;}return ret;}
ll cmp(ll a1,ll b1,ll a2,ll b2){return (i128)a1*b2<=(i128)a2*b1;}
ll inv(ll v,const ll &mod){return ksm(v,mod-2,mod);}
ll CRT(ll a1,ll m1,ll a2,ll m2)
{return (qmul(a1,inv(m2,m1)*m2,m1*m2)+qmul(a2,inv(m1,m2)*m1,m1*m2))%(m1*m2);}
const ll mod1=1e9+7,mod2=1e9+9,mod3=mod1*mod2,mod4=1e9+21,mod5=1e9+33,mod6=mod4*mod5,mod7=1000000087,mod8=1000000093,mod9=mod7*mod8;
bool check(ll p,ll q){if(p>1000000000||q>1000000000)return 0;return 1;}
void solve()
{
ll t1,t2,r;
printf("? %lld\n\n",mod1);fflush(stdout);
scanf("%lld",&t1);
printf("? %lld\n\n",mod2);fflush(stdout);
scanf("%lld",&t2);
r=CRT(t1,mod1,t2,mod2);
ll a1=0,b1=1,a2=1,b2=0;
while(b1<=1e9&&b2<=1e9)
{
ll am=a1+a2,bm=b1+b2;
ll np=qmul(b1,r,mod3),nq=b1;
if(check(np,nq)){printf("! %lld %lld\n",np,nq);fflush(stdout);return;}
if(cmp(am,bm,r,mod3))
{
a1=am,b1=bm;
ll lim=(1e9-b1)/b2;
if(lim)
for(int i=__lg(lim);i>=0;i--)
if((b1+b2*(1<<i)<=1e9)&&cmp(a1+a2*(1<<i),b1+b2*(1<<i),r,mod3))a1=a1+a2*(1<<i),b1=b1+b2*(1<<i);
}
else
{
a2=am,b2=bm;
ll lim=(1e9-b2)/b1;
if(lim)
for(int i=__lg(lim);i>=0;i--)
if((b2+b1*(1<<i)<=1e9)&&!cmp(a2+a1*(1<<i),b2+b1*(1<<i),r,mod3))a2=a2+a1*(1<<i),b2=b2+b1*(1<<i);
}
}
printf("? %lld\n\n",mod4);fflush(stdout);
scanf("%lld",&t1);
printf("? %lld\n\n",mod5);fflush(stdout);
scanf("%lld",&t2);
r=CRT(t1,mod4,t2,mod5);
a1=0,b1=1,a2=1,b2=0;
while(b1<=1e9&&b2<=1e9)
{
ll am=a1+a2,bm=b1+b2;
ll np=qmul(b1,r,mod6),nq=b1;
if(check(np,nq)){printf("! %lld %lld\n",np,nq);fflush(stdout);return;}
if(cmp(am,bm,r,mod6))
{
a1=am,b1=bm;
ll lim=(1e9-b1)/b2;
if(lim)
for(int i=__lg(lim);i>=0;i--)
if((b1+b2*(1<<i)<=1e9)&&cmp(a1+a2*(1<<i),b1+b2*(1<<i),r,mod6))a1=a1+a2*(1<<i),b1=b1+b2*(1<<i);
}
else
{
a2=am,b2=bm;
ll lim=(1e9-b2)/b1;
if(lim)
for(int i=__lg(lim);i>=0;i--)
if((b2+b1*(1<<i)<=1e9)&&!cmp(a2+a1*(1<<i),b2+b1*(1<<i),r,mod6))a2=a2+a1*(1<<i),b2=b2+b1*(1<<i);
}
}
printf("? %lld\n\n",mod7);fflush(stdout);
scanf("%lld",&t1);
printf("? %lld\n\n",mod8);fflush(stdout);
scanf("%lld",&t2);
r=CRT(t1,mod7,t2,mod8);
a1=0,b1=1,a2=1,b2=0;
while(b1<=1e9&&b2<=1e9)
{
ll am=a1+a2,bm=b1+b2;
ll np=qmul(b1,r,mod9),nq=b1;
if(check(np,nq)){printf("! %lld %lld\n",np,nq);fflush(stdout);return;}
if(cmp(am,bm,r,mod9))
{
a1=am,b1=bm;
ll lim=(1e9-b1)/b2;
if(lim)
for(int i=__lg(lim);i>=0;i--)
if((b1+b2*(1<<i)<=1e9)&&cmp(a1+a2*(1<<i),b1+b2*(1<<i),r,mod9))a1=a1+a2*(1<<i),b1=b1+b2*(1<<i);
}
else
{
a2=am,b2=bm;
ll lim=(1e9-b2)/b1;
if(lim)
for(int i=__lg(lim);i>=0;i--)
if((b2+b1*(1<<i)<=1e9)&&!cmp(a2+a1*(1<<i),b2+b1*(1<<i),r,mod9))a2=a2+a1*(1<<i),b2=b2+b1*(1<<i);
}
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("1.out","w",stdout);
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
/*
992240734 979326369
404614179
506026278
832398522
921642416
*/