Guess Divisors Count
Contest: Codeforces Round 643 (Div. 2)
Difficulty rating: 2600
Tags: constructive algorithms, interactive, number theory

This is an interactive problem.

We have hidden an integer $$$1 \le X \le 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 | \le 7$$$;
- $$$\frac{1}{2} \le \frac{ans}{d} \le 2$$$.

You can make at most $$$22$$$ queries. One query consists of one integer $$$1 \le Q \le 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 format:
The first line of input contains one integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of games.

Interaction format:
To make a query print a line "? Q" ($$$1 \le Q \le 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 \le T \le 100$$$) — the number of games.

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

So the example has the form

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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 \le 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 $$$\frac{1}{2} \le \frac{42}{23} \le 2$$$.

Example input:
2

1

1

1


1024

1048576

4194304

Example output:
? 982306799268821872

? 230856864650023977

? 134690134760714371

! 5
? 1024

? 1048576

? 1073741824

! 42

Editorial:
If $$$X = p_{1}^{\alpha_{1}} \cdot p_{2}^{\alpha_{2}} \cdot \ldots \cdot p_{k}^{\alpha_{k}}$$$ then $$$d(X) = (\alpha_{1} + 1) \cdot (\alpha_{2} + 1) \cdot \ldots \cdot (\alpha_{k} + 1)$$$.
If $$$X$$$ has prime $$$p$$$ in power $$$\alpha$$$ and $$$Q$$$ has $$$p$$$ in power $$$\beta$$$ then $$$gcd(X, Q)$$$ will have $$$p$$$ in power $$$\gamma = \min (\alpha, \beta)$$$. If $$$\gamma < \beta$$$ then $$$\alpha = \gamma$$$, otherwise $$$\gamma = \beta$$$ and $$$\alpha \ge \gamma$$$. We don't know $$$X$$$, but we can choose $$$Q$$$. If we'll choose $$$Q$$$ with known prime factorization then we'll be able to extract all the information from query fast (in $$$O(\log Q)$$$).
After all the queries for each prime $$$p$$$ we'll know either the exact power in which $$$X$$$ has it, or lower bound for it. We can get upper bound from the fact that $$$X \le 10^{9}$$$.
It is clear that we cannot get information about all primes — there are too many of them and too few queries. We want to somehow use the fact that we don't have to find the exact answer...
Suppose we have figured out that $$$X = X_{1} \cdot X_{2}$$$ where we know $$$X_{1}$$$ exactly and we also know that $$$X_{2}$$$ has no more than $$$t$$$ prime factors (including multiplicity). Then $$$d(X_{1}) \le d(X) \le d(X_{1}) \cdot d(X_{2}) \le d(X_{1}) \cdot 2^{t}$$$. If $$$t \le 1$$$ then our answer will have relative error no more than $$$0.5$$$...
One of the ways to guarantee that $$$X_{2}$$$ has few prime factors is to show that it cannot have small prime factors. That means that we have to calculate the exact power for all small primes. This gives an overall idea for the solution: let's make a query $$$Q=p^{\beta}$$$ for all primes $$$p \le B$$$ (for some bound $$$B$$$) where $$$\beta$$$ is chosen in such a way that $$$p^{\beta} > 10^{9}$$$. This allows us to know the exact power in which $$$X$$$ has $$$p$$$.
This basic idea can be improved in several ways:
1. $$$X$$$ has no more than 9 different prime factors, so for most primes its power is 0. If we could exclude these redundant primes fast it could speed up the solution significantly. And there is a way: we could make a query $$$Q = p_{1} p_{2} \ldots p_{s}$$$ for $$$s$$$ different primes, after that we will know which of them are factors of $$$X$$$;
2. $$$\beta$$$ can be chosen such that $$$p^{\beta + 1} > 10^{9}$$$, because even if $$$\gamma = \beta$$$ and $$$\alpha \ge \gamma = \beta$$$ we will know that $$$\alpha \le \beta$$$ since otherwise $$$X > 10^{9}$$$;
3. From the previous point follows that we can find the exact power for two primes simultaneously, just make a query with a product of two respective numbers.
How to choose $$$B$$$? Apparently we want $$$B^{2} > 10^{9}$$$. But actually $$$t \le 2$$$ is ok for us: if we know that $$$L \le d(X) \le 4L$$$ then we can answer $$$2L$$$ and the relative error will be no more than $$$0.5$$$. That means we want $$$B^{3} > 10^{9}$$$ or $$$B = 1001$$$.
We are close: there are 168 primes less than 1001, we can check 6 primes (for being a factor of $$$X$$$) in one query since $$$1000^{6} \le 10^{18}$$$, so we need 28 queries.
Let's note that if we have found some prime factors of $$$X$$$ (let's say their product is $$$X_{1}$$$) then $$$X_{2} \le \frac{10^{9}}{X_{1}}$$$. Suppose we have checked all the primes not greater than $$$p$$$ and $$$X_{1} \cdot p^{3} > 10^{9}$$$. That means that $$$X_{2}$$$ has no more than 2 prime divisors and we are good.
What is left is to use our right to have absolute error: if $$$X_{1} \le 3$$$ we can just print 8! Either $$$X_{1} \le 3$$$ and we are fine with $$$X_{2}$$$ having 3 prime factors, or $$$X_{1} \ge 4$$$ and we have to check all primes up to $$$\sqrt[3]{10^{9} / 4} < 630$$$. There are 114 such primes, so we need only 19 queries.
We will also need some queries to find out the exact power for those small prime factors of $$$X$$$ we have found. If we have found no more than 2 prime factors, we'll need 1 query, otherwise we'll have to check primes only up to $$$\sqrt[3]{10^{9} / (2 \cdot 3 \cdot 5)} < 330$$$, of which there are only 66 so the first part of the solution spends no more than 11 queries.
So we have shown that the solution spends no more than 20 queries. We did some rough estimations, the actual bound for this solution is 17 queries.