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' \subseteq S~ satisfy that all given primes ~p~ divide the product of all elements of ~S'~? Output the answer modulo ~998\,244\,353~.

Constraints

~n \le 10^6~

~s_i, p_i \le 2\,000~

~m \le 1\,500~

~\sum c_i \le 18\,000~

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~	~1\,500~	~10^4~	~s_i \le 30~
9, 10, 11	~10^4~	~1\,000~	~5\,000~	~s_i \le 500~
12, 13	~1\,000~	~100~	~1\,000~	None
14, 15, 16, 17	~5\,000~	~600~	~7\,000~	None
18, 19, 20	~10^6~	~1\,500~	~18\,000~	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.