首先一眼 CRT，考虑找几个小质数，然后确定 $x$ 模这些小质数的余数，就可以求出 $x$ 了。

由于确定模质数 $p$ 的余数需要排掉 $p-1$ 个，那肯定是越小的质数越优。我们可以选取 $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 43, 47, 53$ 共 $15$ 个质数，这些质数的积是 $1.05 \times 10^{18}$，浪费较少。

考虑怎么排掉这些数。一个 naive 的想法是随机一些质数，尝试排掉一些余数。但是这样可能余数会重复，其实是很劣的。我们要想办法保证余数不重复。

对于余数唯一确定的数 $p$，假设余数是 $k$，我们如果选出来一个余数 $a$ 使得 $p \mid (a+k)$ 那么一定是合数，因此我们随机选一个其他余数。

对于余数非唯一确定的数 $p$，随机一个未被排除的余数 $k$，选出来一个余数 $a$ 使得 $p \mid (a+k)$，如果得到了质数那么就可以看排掉这个余数。

然后可以拿 CRT 对于这些余数解出这样随出来的 $y$。注意如果 $y>10^{18}$ 不能问。然而这样的概率是比较小的（大约是 $\dfrac{1}{21}$）。时间绰绰有余。

这个做法看起来好像次数挺多，但是实际上效率非常高，实测几乎都跑不到 $7800$ 次。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T, lc[17], z[17], b[17], tlcm;
const int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 43, 47, 53}, pn = 15;
set<int> S[17];
mt19937 eng(time(0));
int qry(int x){
    string res;
    cout << "? " << x << "\n";
    cout.flush();
    cin >> res;
    if (res == "Busted")
        exit(-1);
    return res == "Prime";
}
void rep(int x){
    string res;
    cout << "! " << x << "\n";
    cout.flush();
    cin >> res;
}
void ini(){
    for (int i = 0; i < pn; i++){
        S[i].clear();
        for (int j = 0; j < p[i]; j++)
            S[i].insert(j);
    }
}
int qmul(int x, int y, int mod){
    return (__int128)x * y % mod;
}
int calc(){
    tlcm = 1;
    for (int i = 0; i < pn; i++)
        tlcm *= p[i];
    for (int i = 0; i < pn; i++)
        lc[i] = tlcm / p[i];
    for (int i = 0; i < pn; i++)
        for (int j = 0; ; j++)
            if (lc[i] % p[i] * j % p[i] == 1){
                z[i] = qmul(lc[i], j, tlcm);
                break;
            }
    int ans = 0;
    for (int i = 0; i < pn; i++)
        ans = (ans + qmul(z[i], b[i], tlcm)) % tlcm;
    return ans;
}
void filt(){
    bool fnd = 0;
    while (1){
        int y = eng();
        if (fnd){
            for (int i = 0; i < pn; i++){
                if (S[i].size() == 1){
                    while (1){
                        b[i] = eng() % p[i];
                        if ((b[i] + *S[i].begin()) % p[i])
                            break;
                    }
                    continue;
                }
                while (1){
                    b[i] = eng() % p[i];
                    if (S[i].find((p[i] - b[i]) % p[i]) != S[i].end())
                        break;
                }
            }
            y = calc();
        }
        if (y > 1e18)
            continue;
        int sta = qry(y);
        if (sta){
            fnd = 1;
            bool ppan = 1;
            for (int i = 0; i < pn; i++){
                int vl = y % p[i], rv = (p[i] - vl) % p[i];
                if (S[i].find(rv) != S[i].end())
                    S[i].erase(rv);
                if (S[i].size() > 1)
                    ppan = 0;
            }
            if (ppan)
                break;
        }
    }
    for (int i = 0; i < pn; i++)
        b[i] = *S[i].begin();
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> T;
    while (T--){
        ini();
        filt();
        rep(calc());
    }
    return 0;
}