作为交互题，你可以进行如下操作：询问一堆质数的幂的乘积是否等于 n ，询问一堆质数的幂的乘积与 n 的公因数（对 998244353 取模），输出答案（答案对 998244353 取模）。
最多进行 1050 次操作。
题目解法
Step 1 获取 n
首先看到题目说了次数不超过 10000 且质数个数不超过一千。考虑每次询问他的一个质因子的次幂数，具体的，我们询问 \gcd(p^{10001},n)，得到的值就是 n 的最大的素数 p 因子的幂次，而要求出这个幂次，我们注意到前一千个质数对于 998244353 取模的阶都在 10000 以上，直接暴力找即可。
Step 2 计算 part 1
怎么第二步就计算了
这里我们发现，我们强行令一个 n 的因数 d 成为他的质因子，那么 \varphi(\frac{n}{d}) 就是与 n 公因数为 d 的数的个数，即现在答案转化为 \sum\limits_{d|n}d\times \varphi(\frac{n}{d})。这坨东西看起来不是很好搞，我们考虑再次把欧拉函数拆开。得到了 \sum\limits_{d|n}d\prod\limits_{p|\frac{n}{d},p\in \mathbb{P},\gcd(p^{k+1},\frac{n}{d})=p^k}(p-1)p^{k-1}。
现在再看，我们发现在计算欧拉函数的时候，只要不把某个质因数直接除完，那么这些因数就会出现在 d 上，这种情况下 d\times \varphi(\frac{n}{d})=\varphi(n)。这种情况的数量比较好算。计这部分答案为 res 。
Step 3 计算 part 2
令 p_i 表示第 i 个质数，s_i 表示第 i 个质数在 n 中的次数。
而对于剩下的情况，也就是需要我们把一些质因数完全删除。这一部分我们考虑 dp。具体的，我们令 dp[i] 表示最后一个删完的（按照质因子大小排序）质因子是第 i 个质数的前 i 个质数的贡献，显然这部分贡献由三部分组成——上一个被取完的质因子和其之前的贡献 、中间的没有被用完的贡献、这次删完了的贡献。我们假设上一个被取完的质数是第 j 个质数，则三部分的贡献应分别为 dp[j]、\prod\limits_{k=j+1}^{i-1}\varphi(p_k^{s_k})\times s_k、p_i^{s_i}。一三部分不多赘述，第二部分和上文 part 1 类似。
枚举 j 即可，第二部分容易发现是一个从 i 开始的后缀积，故从后向前枚举直接算即可。
Step 4 整合答案
part 1 和 part 2 无关联，直接加和。
part 2 部分中，对于每一个以这个质数为最后一个被删完的质数的贡献再乘上剩下的没被计算在其中的后 1000-i 个质数的贡献即可。这部分和计算 part 2 中的第二部分一样。