Memory Resonance Calculation

This is an interactive problem.

Little H has lost his memory. His past memories are now fragmented into n memory fragments. A doctor has n sampling strips, where the i-th strip has length i (for i = 1, 2, …, n). When a memory fragment interacts with a sampling strip of length i, they produce an emotional resonance of size \(\gcd(n,i)\). The doctor also possesses a machine which in a query can report:

• TheSame? m: Followed by m lines each containing two numbers \(p_i\) and \(k_i\) (where \(p_i\) is prime and \(k_i\) is a positive integer). The doctor will respond with Yes if the number of memory fragments \(n\) equals \(\prod_{i=1}^m p_i^{k_i}\), and No otherwise.
• GetGCD. m: Followed by m lines each containing two numbers \(p\) and \(k\) (with the same restrictions). The machine returns the emotional resonance produced between the memory fragments and the number \(\prod_{i=1}^m p_i^{k_i}\), which is defined as the appropriate combination of the values \(\gcd(n,i)\) with respect to the product provided.

Once you have determined the total emotional resonance produced when all n sampling strips are used (i.e. the sum \(\sum_{i=1}^{n} \gcd(n,i)\)), you must report your answer using the following output format:

IfoundTheAnswer! m

All interactions and final answers are performed modulo \(998244353\).

Note: For the purpose of this problem, you are provided with n as the input, and you are required to compute and output the value:

[ S(n)=\sum_{i=1}^{n}\gcd(n,i) \pmod{998244353}. ]

inputFormat

The input consists of a single integer n on a line, representing the number of memory fragments.

outputFormat

Output a single integer, denoting the total emotional resonance \(S(n)=\sum_{i=1}^{n}\gcd(n,i)\) modulo \(998244353\).

sample

1

1