Product

Problem

Aizu decided to play a game using a prime number $P$, a set of natural numbers $G$, and a natural number $A$.

First, Aizu writes $1$ on the paper at hand. After that, perform the following series of operations any number of times.

• Select one element from $G$. Let this be $g$.
• Write a new product of the number written on the paper at hand and $g$ on the paper.
• Erase the number originally written on the paper.

If $A$ is equal to the number written on the paper at hand divided by $P$, Aizu wins, otherwise he loses. Determine if Aizu can win when $P$, $G$, and $A$ are given.

Constraints

The input satisfies the following conditions.

• All inputs are integers.
• $2 \ le P \ le 2 ^ {31} -1$
• $1 \ le T, | G | \ le 10 ^ 5$
• $1 \ le G_i, A \ le P-1$
• $G_i \ ne G_j,$ if $i \ ne j$
• The sum of $| G |$ in all test cases does not exceed $10 ^ 5$.

Input

The input is given in the following format.

$P$ $T$ $Test_1$ $\ vdots$ $Test_ {T}$

The input consists of multiple test cases. First, the $1$ line is given the prime number $P$ and the number of test cases $T$. $P$ is common to all test cases. Each test case is given in the following $T$ line.

Each test case is given as follows.

$| G |$ $G_1$ $\ dots$ $G_ {| G |}$ $A$

In each test case, the number of elements of $G$, each element of $G$, and $A$ are given in order, separated by a space.

Output

For each test case, if Aizu can win, $1$ will be output on one line, otherwise $0$ will be output on one line.

Examples

Input

7 3 1 1 2 1 2 1 3 1 2 4 5

Output

0 1 0

Input

1000000007 8 3 2 9 7 5 3 2 9 5 1000001 3 39 1002 65537 12 2 1000000006 518012930 793649232 10 459268180 313723762 835892239 612038995 90424474 366392946 38051435 854115735 5132833 320534710 421820264 1 1 1 1 1 1000000006 1 1000000006 1

Output

0 1 1 1 0 1 0 1

inputFormat

input satisfies the following conditions.

• All inputs are integers.
• $2 \ le P \ le 2 ^ {31} -1$
• $1 \ le T, | G | \ le 10 ^ 5$
• $1 \ le G_i, A \ le P-1$
• $G_i \ ne G_j,$ if $i \ ne j$
• The sum of $| G |$ in all test cases does not exceed $10 ^ 5$.

Input

The input is given in the following format.

$P$ $T$ $Test_1$ $\ vdots$ $Test_ {T}$

The input consists of multiple test cases. First, the $1$ line is given the prime number $P$ and the number of test cases $T$. $P$ is common to all test cases. Each test case is given in the following $T$ line.

Each test case is given as follows.

$| G |$ $G_1$ $\ dots$ $G_ {| G |}$ $A$

In each test case, the number of elements of $G$, each element of $G$, and $A$ are given in order, separated by a space.

outputFormat

Output

For each test case, if Aizu can win, $1$ will be output on one line, otherwise $0$ will be output on one line.

Examples

Input

7 3 1 1 2 1 2 1 3 1 2 4 5

Output

0 1 0

Input

1000000007 8 3 2 9 7 5 3 2 9 5 1000001 3 39 1002 65537 12 2 1000000006 518012930 793649232 10 459268180 313723762 835892239 612038995 90424474 366392946 38051435 854115735 5132833 320534710 421820264 1 1 1 1 1 1000000006 1 1000000006 1

Output

0 1 1 1 0 1 0 1

样例

1000000007 8
3 2 9 7 5
3 2 9 5 1000001
3 39 1002 65537 12
2 1000000006 518012930 793649232
10 459268180 313723762 835892239 612038995 90424474 366392946 38051435 854115735 5132833 320534710 421820264
1 1 1
1 1 1000000006
1 1000000006 1

0
1
1
1
0
1
0
1

</p>