_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 $a n s$ 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:
You can make at most 22 queries. One query consist of one integer $1 <= Q <= 10^(18)$. In response you will get $g c d (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$.
The first line of input contains one integer $T$ ($1 <= T <= 100$) — the number of games.
To make a query print a line "_? Q_" ($1 <= Q <= 10^(18)$). After that read one integer $g c d (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. $a n s$ 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 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:
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 thin 244 thin 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 thin 244 thin 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 thin 194 thin 304 = 2^(22)$ is hidden, it has 23 divisors. The solution has made queries $1024 = 2^(10)$, $1 thin 048 thin 576 = 2^(20)$, $1 thin 073 thin 741 thin 824 = 2^(30)$ and got responses $1024 = 2^(10)$, $1 thin 048 thin 576 = 2^(20)$, $4 thin 194 thin 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 $frac(1, 2) <= frac(42, 23) <= 2$.
## 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 $g c d (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. $a n s$ 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 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.
[samples]
## 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 thin 244 thin 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 thin 244 thin 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 thin 194 thin 304 = 2^(22)$ is hidden, it has 23 divisors. The solution has made queries $1024 = 2^(10)$, $1 thin 048 thin 576 = 2^(20)$, $1 thin 073 thin 741 thin 824 = 2^(30)$ and got responses $1024 = 2^(10)$, $1 thin 048 thin 576 = 2^(20)$, $4 thin 194 thin 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 $frac(1, 2) <= frac(42, 23) <= 2$.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of games, with $ 1 \leq T \leq 100 $.
For each game $ k \in \{1, \dots, T\} $, let $ X_k \in \mathbb{Z} $ be a fixed hidden integer with $ 1 \leq X_k \leq 10^9 $.
Let $ d_k = \tau(X_k) $ denote the number of positive divisors of $ X_k $.
**Constraints**
1. You may make at most 22 queries per game.
2. Each query is an integer $ Q $ with $ 1 \leq Q \leq 10^{18} $.
3. Upon querying $ Q $, you receive $ \gcd(X_k, Q) $.
4. The interactor is non-adaptive: $ X_k $ is fixed before any queries in game $ k $.
**Objective**
For each game $ k $, output an integer $ \text{ans}_k $ such that **at least one** of the following holds:
- $ |\text{ans}_k - d_k| \leq 7 $,
- $ \frac{1}{2} \leq \frac{\text{ans}_k}{d_k} \leq 2 $.
After outputting $ \text{ans}_k $, proceed to the next game (or terminate if $ k = T $).