Background

X is playing with L. They walked into a park and found a very strange towering tree. Following the habits of OIers, this tree has a clear feature: it is heavily right-skewed.

Problem Description

X thought of another thing that is also heavily right-skewed.

First, he writes down a number $n$.

Next, for every divisor $x$ of $n$ with $x\notin\{1,n\}$, make these $x$ become the children of $n$, in increasing order.

Build the tree recursively in this way, and the tree is completed. X calls this tree an “$n$-th mathematical tree”. X wants to know: given $q$ positive integers $x$, how many times does each of them appear in the $n$-th mathematical tree.

Since $n$ is very large, he can only tell you the prime factorization of $n$.

Output the answers modulo $998244353$.

Input Format

The first line contains several pairs of integers $(a_i,b_i)$, meaning that $n=\prod a_i^{b_i}$, and ends with 0 0. It is guaranteed that $a_i$ is prime and $b_i\in N^*$.

The second line contains one integer $q$, with the meaning as described above.

The third line contains $q$ integers, representing the $q$ queries for this testdata.

Output Format

Output one line with $q$ integers, where each is the answer for the corresponding query modulo $998244353$.

2 3 3 1 0 0
1
2

8

2 3 3 1 0 0
3
3 5 7

4 0 0

7 3 0 0
3
49 1 343

1 0 1

Hint

Sample explanation: the first two sets of testdata are both the $24$-th mathematical tree. After drawing, the tree is as follows:

Among them, $2$ appears $8$ times, $3$ appears $4$ times, and $5,7$ do not appear.

For the third set of testdata, note that $343$ appears once at the root of the $343$-th mathematical tree, and $1$ will not appear in the mathematical tree.

For $100\%$ of the data, $1\le b_i \le 5000$, $\sum b_i\le5000$, $2\le a_i\le 10^9$, $1\le x\le 10^{18}$.

Translated by ChatGPT 5