Little A has $n$ cards, numbered $1, 2, \dots, n$. Each card has a positive integer written on it, where the integer on the $i$-th card is $s_i$.

There are $m$ rounds of a game. In the $i$-th round, $c_i$ prime numbers are given. Little A needs to choose any number of cards such that the product of the integers on these cards is divisible by every prime number given for that round.

This is certainly not difficult for Little A, so he starts thinking about a harder problem: for each round of the game, how many ways are there to choose the cards?

Little A is stumped, so he asks for your help. You only need to tell him the answer modulo $998244353$. Two choices A and B are considered different if and only if there exists a card that is chosen in A but not in B, or there exists a card that is chosen in B but not in A. Note: two cards with the same number written on them but different indices are considered different cards.

Input

The first line contains a positive integer $n$, representing the number of cards. The second line contains $n$ positive integers $s_i$, representing the number written on each card. The third line contains a positive integer $m$, representing the number of game rounds. The next $m$ lines each contain the first positive integer $c_i$, representing the number of prime numbers given for that round, followed by $c_i$ prime numbers $p_{i,j}$, representing all the prime numbers given for that round. It is guaranteed that $\sum_i c_i \le 18000$, i.e., the sum of all $c_i$ does not exceed $18000$.

Output

Output $m$ lines, each containing an integer, where the $i$-th line represents the number of ways for the $i$-th round modulo $998244353$.

Examples

Input 1

5
2 10 2 10 5 46
4
2 2 5
2 2 23
1 3
1 23

Output 1

27
16
0
16

Note 1

First round: All schemes are valid except for the following 5: choosing nothing, choosing 2, choosing 5, choosing 46, and choosing 2 and 46. So the answer is $2^5 - 5 = 27$. Second round: As long as 46 is chosen, other cards can be chosen or not, so the answer is $2^4 = 16$.

Constraints

For $100\%$ of the data, $n \le 10^6$, $s_i \le 2000$, $m \le 1500$, $\sum_i c_i \le 18000$, $2 \le p_{i,j} \le 2000$.