K. Prime Coloring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$ and $$$k$$$ distinct prime numbers $$$p_1, p_2, \ldots, p_k$$$.

You color each of the integers $$$1, 2, \ldots, n$$$ with one of two colors, $$$0$$$ or $$$1$$$. Such a coloring is good if, for every index $$$i$$$ ($$$1 \le i \le k$$$) and every positive integer $$$x$$$ with $$$p_i \cdot x \le n$$$, the integers $$$x$$$ and $$$p_i \cdot x$$$ receive different colors.

In addition, the colors of some integers are fixed in advance. You are given $$$m$$$ pairs $$$(v_1, c_1), (v_2, c_2), \ldots, (v_m, c_m)$$$. A coloring is valid if it is good and, for every index $$$j$$$ ($$$1 \le j \le m$$$), the integer $$$v_j$$$ has color $$$c_j$$$.

Count the number of valid colorings. Since the answer can be large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 16$$$) — the number of integers to color and the number of primes.

The second line contains $$$k$$$ distinct prime numbers $$$p_1, p_2, \ldots, p_k$$$ ($$$2 \le p_i \le 10^9$$$) — the given primes.

The third line contains a single integer $$$m$$$ ($$$0 \le m \le 3 \cdot 10^5$$$) — the number of integers whose color is fixed.

The $$$j$$$-th of the next $$$m$$$ lines contains two integers $$$v_j$$$ and $$$c_j$$$ ($$$1 \le v_j \le n$$$, $$$c_j \in \{0, 1\}$$$) — the integer $$$v_j$$$ is fixed to the color $$$c_j$$$. The values $$$v_1, v_2, \ldots, v_m$$$ are distinct.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the number of valid colorings, modulo $$$998244353$$$.

Example
Input
2
4 1
2
1
1 0
6 2
2 3
2
2 0
6 0
Output
2
0
Note

In the first test case, $$$n = 4$$$, the only prime is $$$2$$$, and the color of $$$1$$$ is fixed to $$$0$$$. There are exactly two valid colorings; giving the colors of $$$1, 2, 3, 4$$$ in order, they are $$$(0, 1, 0, 0)$$$ and $$$(0, 1, 1, 0)$$$. In each, $$$1$$$ and $$$2$$$ have different colors, $$$2$$$ and $$$4$$$ have different colors, and $$$1$$$ has color $$$0$$$.

In the second test case, $$$n = 6$$$ and the primes are $$$2$$$ and $$$3$$$. The colors of $$$2$$$ and $$$6$$$ are both fixed to $$$0$$$, but $$$6 = 3 \cdot 2 \le 6$$$, so a good coloring must give them different colors — a contradiction. Hence no valid coloring exists and the answer is $$$0$$$.