P9438 『XYGOI round1』Many Divisors.

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**.

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$.

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 one line with $q$ integers, where each is the answer for the corresponding query modulo $998244353$.

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. | Subtask | $n$ | $q$ | Guaranteed that $n$ is a prime power | Score | |:-:|:-:|:-:|:-:|:-:| |0|$\le 10^3$|$\le 20$|Yes|10| |1|$\le 10^6$|$\le 20$|No|10| |2|$\sum b_i\le5000$|$\le 20$|Yes|40| |3|$\sum b_i\le5000$|$\le 20$|No|40| 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