Tommy has a multiset of $n$ positive integers $S=\{s_1,s_2,\dots ,s_n\}$ and $m$ queries. In query $i$, he has $c_i$ prime numbers $p_1,p_2,\dots ,p_{c_i}$ and asks: how many multisets $S^{\prime }\subseteq S$ satisfy that all given primes $p$ divide the product of all elements of $S^{\prime }$? Output the answer modulo $998244353$.

Constraints

$n\le {10}^6$

$s_i,p_i\le 2000$

$m\le 1500$

$\sum c_i\le 18000$

Test	$n\le$	$m\le$	$\sum c_i\le$	Other restrictions
1, 2	$10$	$10$	$20$	$s_i\le 30$
3, 4, 5	$10$	$20$	$50$	None
6, 7, 8	${10}^6$	$1500$	${10}^4$	$s_i\le 30$
9, 10, 11	${10}^4$	$1000$	$5000$	$s_i\le 500$
12, 13	$1000$	$100$	$1000$	None
14, 15, 16, 17	$5000$	$600$	$7000$	None
18, 19, 20	${10}^6$	$1500$	$18000$	None

Input Specification

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $s_1,s_2,\dots ,s_n$.

The third line contains a positive integer $m$.

The next $m$ lines begin with a positive integer $c_i$. $c_i$ primes follow, describing a query.

Output Specification

Output $m$ lines, corresponding to the answer for the corresponding query.

Sample Input 1

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

Sample Output 1

27
16
0
16

Attachments

Attachments can be found here.