CF1355F.Guess Divisors Count

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$.

这是一个交互式问题。

我们隐藏了一个整数 $1 \le X \le 10^{9}$。你无需猜出该数本身，而只需估计该数的正约数个数；甚至无需给出精确值：只要你的答案的绝对误差不超过 7，或相对误差不超过 $0.5$，即视为正确。更准确地说，设你的答案为 $ans$，$X$ 的约数个数为 $d$，则当且仅当以下两个条件中至少一个成立时，你的答案被视为正确：

• $| ans - d | \le 7$；
• $\frac{1}{2} \le \frac{ans}{d} \le 2$。

你最多可进行 $22$ 次询问。每次询问包含一个整数 $1 \le Q \le 10^{18}$，系统将返回 $\gcd(X, Q)$ —— 即 $X$ 与 $Q$ 的最大公约数。

整数 $X$ 在所有询问开始前即已固定（即交互器是非自适应的）。

我们将“估计整数 $X$ 的约数个数”这一过程称为一局游戏。在单个测试用例中，你需要进行 $T$ 局独立的游戏，即对 $T$ 个相互独立的 $X$ 值，分别估计其约数个数。

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

输入的第一行包含一个整数 $T$（$1 \le T \le 100$）—— 游戏的局数。

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$.

为什么查询次数的限制恰好是 22 次？也许出题人是泰勒·斯威夫特（Taylor Swift）的粉丝。

我们来看这个例子。

在第一局游戏中，隐藏的数为 $X = 998\,244\,353$。猜中这个数恐怕很难吧？该数是质数，因此其约数个数为 2。解法进行了若干次随机查询，而所有响应结果均为 1（奇怪的现象：三次随机选取的数中竟无一能被 $998\,244\,353$ 整除）。由此合理推测：隐藏数字的约数个数并不多，于是解法回答了 5。为什么不呢？该答案会被判为正确，因为 $| 5 - 2 | = 3 \le 7$。

在第二局游戏中，隐藏的数为 $X = 4\,194\,304 = 2^{22}$，它共有 23 个约数。解法依次查询了 $1024 = 2^{10}$、$1\,048\,576 =2^{20}$、$1\,073\,741\,824 = 2^{30}$，得到的响应分别为 $1024 = 2^{10}$、$1\,048\,576 =2^{20}$、$4\,194\,304 = 2^{22}$。随后解法彻底陷入困惑，给出了“生命、宇宙以及一切终极问题的答案”。该答案将被判为正确，因为 $\frac{1}{2} \le \frac{42}{23} \le 2$。