Background

“Ding ding ding,” the class bell rang. After a burst of dizziness, Little H suddenly fell to the ground. In a blur, he could only vaguely feel someone rushing over.

“Where is this? Wasn’t I in class?” Little H looked around.

“Welcome to the OI world. I’m responsible for helping you get familiar with the OI world.” A strange person walked over.

“The OI world?”

“Yes. There are no regular cultural classes here. You can study OI here as much as you want.” The person explained.

Right after that, the person brought Little H to someone who claimed to be a psychologist.

“What are you doing?” Little H stared at the psychologist, who was about to put a strange device on Little H’s head.

“This can help you recover your memories from the whk world.” The psychologist said calmly.

After the device was put on, Little H shouted, “I remember everything!”

But did he really remember everything...

From the moment that person took Little H to visit the OI world, everything became a mess...

Problem Description

This is an interactive problem.

Little H has lost his memory.

Now, Little H’s past memories have turned into $n$ memory fragments. The doctor has $n$ sampling strips of different lengths (lengths are $1\dots n$). A memory fragment will produce an emotional resonance of size $\gcd(n,i)$ with a sampling strip of length $i$.

The doctor has a machine that can measure the emotional resonance size produced by a sampling strip of length $i$ with Little H. Now you may use this machine to measure a limited number of times. The doctor hopes you can tell him: if all $n$ strip lengths are used up, how large the total emotional resonance will be.

Interaction Format

You can ask the doctor using the following format:

TheSame? m: followed by $m$ lines, each line contains two numbers $p_i,k_i$. The doctor will tell you whether the number of Little H’s memory fragments is equal to $\displaystyle\prod_{i=1}^mp_i^{k_i}$. Yes means equal, and No means not equal.

GetGCD. m: followed by $m$ lines, each line contains two numbers $p,k$. The doctor will tell you the emotional resonance size between $\displaystyle\prod_{i=1}^mp_i^{k_i}$ and Little H’s memory fragments.

All queried $p_i$ are primes, and $k_i$ are positive integers. If you do not satisfy the constraints above, the interaction library is not guaranteed to behave as expected.

You can tell the doctor what you know using the following format:

IFoundTheAnswer! m: use this to tell the judge that you already know the total emotional resonance size is $m$, and it will check whether it is correct.

In total, you can interact with the doctor at most $1050$ times. All outputs of the interaction library and the answers you output should be taken modulo $998244353$.

You need to output to standard output, representing what you ask.

After each query, you must flush the buffer, otherwise you may get TLE for no reason.

You may use the following statements to flush the buffer:

• For C/C++: fflush(stdout)；
• For C++: std::cout << std::flush；
• For Java: System.out.flush()；
• For Python: stdout.flush()；
• For Pascal: flush(output)；
• For other languages, please check the documentation of that language.

In particular, for C++, if you output a newline using std::endl instead of '\n', it will also flush the buffer automatically.

Then you need to read from standard input, representing the result returned by the judge.

Input Format

See “Interaction Format”.

Output Format

See “Interaction Format”.

1
No
2
Yes

GetGCD. 0
TheSame?  0
GetGCD. 1
2 1
TheSame? 1
2 1
IFoundTheAnswer! 3

Hint

【Constraints】

“This problem uses bundled tests.”

• $\texttt{Subtask 1(10 pts)：}1 \le\ n\le 500$；
• $\texttt{Subtask 2(25 pts)：}1 \le\ n\le 10^6$；
• $\texttt{Subtask 3(25 pts)：}$it is guaranteed that the unique factorization of $n$ only involves the first $100$ primes；
• $\texttt{Subtask 4(40 pts)：}$no special restrictions.

For $100\%$ of the testdata, the number of primes in the unique factorization of $n$ is at most $1000$, the largest prime factor is at most $7919$ (note: $7919$ is the $1000$-th prime), and the exponent of each prime is at most $10000$.

【Other Hints】

Because the interaction library is not very efficient, the code of the interaction library is provided in the attachment. If you want to use the interaction library code below for debugging, you can download the testlib.h header file in the official SPJ Instructions, then connect the outputs and inputs of the two programs to another program. Of course, you can also simulate the interaction library’s computation and manually type the results into your program.

Translated by ChatGPT 5