Background

For the needs of this problem, we redefine multiplicative functions: it is not guaranteed that $f(1)=1$.

Problem Description

This is a non-traditional problem.

You are given a multiplicative function $f(d)$. For each test point, we will provide in the attachment the values of $g(n)=\sum_{d|n}f(d)$ for $k$ selected terms $\bmod\ 998244353$, and this part will also appear in the input. Then, for each test point, there are $t$ queries. For each query, an integer $d$ is given; please output the value of $f(d)\bmod 998244353$.

Input Format

The first line contains $k$. Each of the next lines contains two positive integers, $d$ and $g(d)$.

Then two numbers $t, id$ are given, representing the number of queries and the test point ID. For each query, one positive integer $n$ is given.

Output Format

For each query, output one non-negative integer representing the answer.

10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

3 -1
1
2
3

1
1
2

Hint

Sample Explanation

Since $g(d)=d$, we have $f(d)=\varphi(d)$, so the result is correct.

Constraints

For each test point:

If you correctly answer the testdata with $n\le k$, you will get $20\%$ of the score.

If you correctly answer all testdata, you will get the remaining $80\%$. So, if you cannot answer correctly, please output a random number to keep the format correct.

Constraints

Translated by ChatGPT 5