Counting Occurrences in the n-th Math Tree

Little X has invented a peculiar recursive structure he calls the n-th math tree. The construction is as follows: first, he writes down a positive integer \(n\). Then, for every proper divisor \(x\) of \(n\) with \(x \notin \{1,n\}\), he attaches \(x\) as a child of \(n\) (the children are arranged in increasing order). This procedure is then applied recursively to every new node: for any node with value \(v\), its children are all proper divisors of \(v\) (i.e. all divisors of \(v\) except 1 and \(v\) itself), arranged in increasing order. The process stops when no proper divisors exist (for example, when \(v\) is prime).

Given that \(n\) may be huge, Little X does not provide \(n\) itself but its prime factorization, namely \[ n=\prod_{i=1}^k p_i^{a_i}, \] where \(p_i\) are primes and \(a_i\) are positive integers.

Your task is, for each of \(q\) queries, to determine how many times a given positive integer \(x\) appears in the n-th math tree. Since the answer can be very large, output it modulo \(998244353\).

Note: The n-th math tree includes the root node \(n\) (which appears exactly once) and then, for every node with value \(v\), its children are defined as all divisors \(d\) of \(v\) such that \(d\mid v\) and \(d\neq 1\) and \(d\neq v\>.

Example: Let \(n=12=2^2\cdot3^1\). Its divisors (other than 1 and 12) are \(2,3,4,6\). The tree starts at 12, and its direct children are 2, 3, 4, 6. Then, for instance, 6 has proper divisors 2 and 3 so that 2 (and 3) appear also in a deeper level. Thus, the number 2 appears in two different chains: directly (12 \(\to\) 2) and via 6 (12 \(\to\) 6 \(\to\) 2); similarly, 4 appears once and 3 appears twice. Also, note that 1 never appears in the tree.

inputFormat

The input begins with an integer \(k\) \( (1 \le k \le 10)\) which is the number of distinct prime factors of \(n\). Each of the next \(k\) lines contains two space‐separated integers \(p\) and \(a\) indicating that \(p\) is a prime and \(n\) has a factor \(p^a\) \( (1 \le a \le 10)\). It is guaranteed that all \(p\) are prime.

The next line contains a positive integer \(q\) \((1 \le q \le 10^5)\) – the number of queries. Each of the following \(q\) lines contains a positive integer \(x\). For each query, you are to compute the number of times \(x\) occurs in the n-th math tree (output 0 if \(x\) is not a divisor of \(n\) or if \(x=1\)).

outputFormat

Output \(q\) lines. The \(i\)-th line should contain a single integer, the number of occurrences of \(x\) in the tree modulo \(998244353\).

sample

2
2 2
3 1
5
12
6
4
3
2

1
1
1
2
3