Problem: This is an interactive problem.

We have hidden an integer 1 ≤ X ≤ 10^{9}. You don't have to guess this number. You have to find the number of divisors of this number, and you don't even have to find the exact number: your answer will be considered correct if its absolute error is not greater than 7 or its relative error is not greater than 0.5. More formally, let your answer be ans and the number of divisors of X be d, then your answer will be considered correct if at least one of the two following conditions is true:

  * | ans - d | ≤ 7;
  * 1/2 ≤ ans/d ≤ 2.



You can make at most 22 queries. One query consists of one integer 1 ≤ Q ≤ 10^{18}. In response, you will get gcd(X, Q) — the greatest common divisor of X and Q.

The number X is fixed before all queries. In other words, interactor is not adaptive.

Let's call the process of guessing the number of divisors of number X a game. In one test you will have to play T independent games, that is, guess the number of divisors T times for T independent values of X.

Input

The first line of input contains one integer T (1 ≤ T ≤ 100) — the number of games.

Interaction

To make a query print a line "? Q" (1 ≤ Q ≤ 10^{18}). After that read one integer gcd(X, Q). You can make no more than 22 such queries during one game.

If you are confident that you have figured out the number of divisors of X with enough precision, you can print your answer in "! ans" format. ans have to be an integer. If this was the last game, you have to terminate the program, otherwise you have to start the next game immediately. Note that the interactor doesn't print anything in response to you printing answer.

After printing a query do not forget to output end of line and flush the output. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Hacks

To hack, use the following format:

The first line contains one integer T (1 ≤ T ≤ 100) — the number of games.

Each of the next T lines contains one integer X (1 ≤ X ≤ 10^{9}) — the hidden number.

So the example has the form 
    
    
      
    2  
    998244353  
    4194304  
    

Example

Input


2

1

1

1


1024

1048576

4194304


Output



? 982306799268821872

? 230856864650023977

? 134690134760714371

! 5
? 1024

? 1048576

? 1073741824

! 42

Note

Why the limitation for number of queries is 22 exactly? Maybe the problem author is a Taylor Swift fan.

Let's look at the example.

In the first game X = 998 244 353 is hidden. Would be hard to guess this, right? This number is prime, so the number of its divisors is 2. The solution has made several random queries, and all the responses turned out to be 1 (strange things, not even one of three random numbers is divisible by 998 244 353). It's fare to assume that the hidden number doesn't have many divisors, so the solution has answered 5. Why not. This answer will be considered correct since | 5 - 2 | = 3 ≤ 7.

In the second game X = 4 194 304 = 2^{22} is hidden, it has 23 divisors. The solution has made queries 1024 = 2^{10}, 1 048 576 =2^{20}, 1 073 741 824 = 2^{30} and got responses 1024 = 2^{10}, 1 048 576 =2^{20}, 4 194 304 = 2^{22}, respectively. Then the solution got completely confused and answered the answer to The Ultimate Question of Life, the Universe, and Everything. This answer will be considered correct since 1/2 ≤ 42/23 ≤ 2.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
const long long mod = 1000000007;
long long rnd(long long x) { return (unsigned long long)mrand() % x; }
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res % mod;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
const std::vector<std::pair<int, int>> moves{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
inline int bitCount(int x) { return __builtin_popcount(x); }
inline int bitCount(long long x) { return __builtin_popcountll(x); }
inline int highestOneBit(int x) { return 1 << (31 - __builtin_clz(x | 1)); }
inline int binaryDigits(int x) { return 32 - __builtin_clz(x | 1); }
template <typename A>
string to_string(A* ptr) {
  stringstream ss;
  ss << "0x" << std::setw(16) << std::setfill('0') << std::hex
     << (uint64_t)(uintptr_t)ptr;
  return ss.str();
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
namespace Factor {
const int N = 1010000;
long long C, fac[10010], n, mut, a[1001000];
int T, cnt, i, l, prime[N], p[N], psize, _cnt;
long long _e[100], _pr[100];
vector<long long> d;
inline long long mul(long long a, long long b, long long p) {
  if (p <= 1000000000)
    return a * b % p;
  else if (p <= 1000000000000ll)
    return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
  else {
    long long d = (long long)floor(a * (long double)b / p + 0.5);
    long long ret = (a * b - d * p) % p;
    if (ret < 0) ret += p;
    return ret;
  }
}
void prime_table() {
  int i, j, tot, t1;
  for (i = 1; i <= psize; i++) p[i] = i;
  for (i = 2, tot = 0; i <= psize; i++) {
    if (p[i] == i) prime[++tot] = i;
    for (j = 1; j <= tot && (t1 = prime[j] * i) <= psize; j++) {
      p[t1] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
void init(int ps) {
  psize = ps;
  prime_table();
}
long long powl(long long a, long long n, long long p) {
  long long ans = 1;
  for (; n; n >>= 1) {
    if (n & 1) ans = mul(ans, a, p);
    a = mul(a, a, p);
  }
  return ans;
}
bool witness(long long a, long long n) {
  int t = 0;
  long long u = n - 1;
  for (; ~u & 1; u >>= 1) t++;
  long long x = powl(a, u, n), _x = 0;
  for (; t; t--) {
    _x = mul(x, x, n);
    if (_x == 1 && x != 1 && x != n - 1) return 1;
    x = _x;
  }
  return _x != 1;
}
bool miller(long long n) {
  if (n < 2) return 0;
  if (n <= psize) return p[n] == n;
  if (~n & 1) return 0;
  for (int j = 0; j <= 7; j++)
    if (witness(rand() % (n - 1) + 1, n)) return 0;
  return 1;
}
long long gcd(long long a, long long b) {
  long long ret = 1;
  while (a != 0) {
    if ((~a & 1) && (~b & 1))
      ret <<= 1, a >>= 1, b >>= 1;
    else if (~a & 1)
      a >>= 1;
    else if (~b & 1)
      b >>= 1;
    else {
      if (a < b) swap(a, b);
      a -= b;
    }
  }
  return ret * b;
}
long long rho(long long n) {
  for (;;) {
    long long X = rand() % n, Y, Z, T = 1, *lY = a, *lX = lY;
    int tmp = 20;
    C = rand() % 10 + 3;
    X = mul(X, X, n) + C;
    *(lY++) = X;
    lX++;
    Y = mul(X, X, n) + C;
    *(lY++) = Y;
    for (; X != Y;) {
      long long t = X - Y + n;
      Z = mul(T, t, n);
      if (Z == 0) return gcd(T, n);
      tmp--;
      if (tmp == 0) {
        tmp = 20;
        Z = gcd(Z, n);
        if (Z != 1 && Z != n) return Z;
      }
      T = Z;
      Y = *(lY++) = mul(Y, Y, n) + C;
      Y = *(lY++) = mul(Y, Y, n) + C;
      X = *(lX++);
    }
  }
}
void _factor(long long n) {
  for (int i = 0; i < cnt; i++) {
    if (n % fac[i] == 0) n /= fac[i], fac[cnt++] = fac[i];
  }
  if (n <= psize) {
    for (; n != 1; n /= p[n]) fac[cnt++] = p[n];
    return;
  }
  if (miller(n))
    fac[cnt++] = n;
  else {
    long long x = rho(n);
    _factor(x);
    _factor(n / x);
  }
}
void dfs(long long x, int dep) {
  if (dep == _cnt)
    d.push_back(x);
  else {
    dfs(x, dep + 1);
    for (int i = 1; i <= _e[dep]; i++) dfs(x *= _pr[dep], dep + 1);
  }
}
void norm() {
  sort(fac, fac + cnt);
  _cnt = 0;
  for (int i = 0; i < cnt; ++i)
    if (i == 0 || fac[i] != fac[i - 1])
      _pr[_cnt] = fac[i], _e[_cnt++] = 1;
    else
      _e[_cnt - 1]++;
}
vector<long long> getd() {
  d.clear();
  dfs(1, 0);
  return d;
}
vector<long long> factor(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  return getd();
}
vector<pair<long long, long long>> factorG(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  vector<pair<long long, long long>> d;
  for (int i = 0; i < _cnt; i++) d.push_back(make_pair(_pr[i], _e[i]));
  return d;
}
bool is_primitive(long long a, long long p) {
  assert(miller(p));
  vector<pair<long long, long long>> D = factorG(p - 1);
  for (int i = 0; i < ((int)(D).size()); i++)
    if (powl(a, (p - 1) / D[i].first, p) == 1) return 0;
  return 1;
}
}  // namespace Factor
int remained;
long long query(long long x) {
  remained--;
  assert(remained >= 0);
  cout << "? " << x << '\n';
  cout.flush();
  long long n;
  cin >> n;
  return n;
}
vector<long long> a;
void solve() {
  remained = 22;
  vector<int> need;
  vector<int> phi;
  for (auto x : a) {
    assert(remained);
    long long m = query(x);
    auto p = Factor::factorG(m);
    for (auto [elem, nbElem] : p) {
      need.emplace_back(elem);
    }
    if ((((int)(need).size()) + 1) / 2 >= remained) break;
  }
  if (((int)(need).size()) & 1) need.emplace_back(998244353);
  for (int i = 0; i < ((int)(need).size()); i += 2) {
    int _a = 1, _b = 1;
    while ((int)1e9 / _a >= need[i]) _a *= need[i];
    while ((int)1e9 / _b >= need[i + 1]) _b *= need[i + 1];
    42;
    if (remained == 0) break;
    long long m = query(1LL * _a * _b);
    auto p = Factor::factorG(m);
    for (auto [elem, nbElem] : p) {
      phi.emplace_back(nbElem);
    }
  }
  int ans = 1;
  for (auto x : phi) ans *= (x + 1);
  cout << "! " << max(8, ans * 2) << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  Factor::init(101000);
  int index = 1;
  long long num = 1LL;
  while (((int)(a).size()) < 25) {
    if ((long long)1e18 / num >= Factor::prime[index])
      num *= Factor::prime[index];
    else {
      a.emplace_back(num);
      num = Factor::prime[index];
    }
    ++index;
  }
  int _;
  cin >> _;
  while (_--) {
    solve();
  }
}