Problem Background

Xiao X and Xiao L are playing together. They walked to a park and found a strangely shaped towering tree. This tree, according to the habits of OIers, has a distinct feature: it is severely right-leaning.

Problem Description

Xiao X thought of another thing that is severely right-leaning.

First, he writes down a number \( n \).

Then, for all divisors \( x \notin \{1, n\} \) of \( n \), let \( x \) become the child node of \( n \) in ascending order.

Recursively construct this tree, and it is built. Xiao X calls this tree a "Number Tree of \( n \)". Xiao X wants to know, given \( q \) positive integers \( x \), how many times each \( x \) appears in the Number Tree of \( n \).

Because \( n \) is very large, he can only tell you the prime factorization of \( n \).

The answer should be taken modulo \( 998244353 \).

Input Format

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

The second line contains an integer \( q \), as described in the problem statement.

The third line contains \( q \) integers, representing the \( q \) queries for this dataset.

Output Format

Output one line with \( q \) integers, representing the answer to each query modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

2 3 3 1 0 0
1
2

Sample Output #1

8

Sample Input #2

2 3 3 1 0 0
3
3 5 7

Sample Output #2

4 0 0

Sample Input #3

7 3 0 0
3
49 1 343

Sample Output #3

1 0 1

Notes

Explanation of the samples: The first two datasets are both Number Trees of \( 24 \). The tree looks like this when drawn:

Here, \( 2 \) appears \( 8 \) times, \( 3 \) appears \( 4 \) times, and \( 5, 7 \) do not appear.

For the third dataset, note that \( 343 \) appears once at the root of the Number Tree of \( 343 \), and \( 1 \) does not appear in the Number Tree.

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

见题面 Input 部分

见题面 Output 部分