Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=int(0);i<int(n);++i)
using namespace std;

using ll=long long;

#define error(args...) { vector<string> _debug = split(#args, ',');err(begin(_debug), args);}

vector<string> split(const string& s, char c){
	vector<string> v;stringstream ss(s);string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {cerr << endl;}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a,Args... args){
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << " ",err(++it, args...);
}

vector<int> primes;
int p, phi;

inline int power(int a, int x){
	int b = 1;
	while(x){
		if(x & 1) b = 1LL * b * a % p;
		a = 1LL * a * a % p;
		x >>= 1; 
	}
	return b;
}

void init(){
	phi = p - 1;
	ll cur = phi;
	for(ll i = 2LL; i * i <= cur; ++i){
		if(cur % i) continue;
		ll tmp = 1LL;
		while(cur % i == 0){
			tmp *= i;
			primes.push_back(tmp);
			cur /= i;
		}
	}
	if(cur != 1) primes.push_back(cur);
}

inline ll gcd(ll a,ll b){
	if(b == 0) return a;
	return gcd(b, a % b);
}

inline ll lcm(ll a, ll b){
	return a / gcd(a,b) * b;
}

ll calc(int val){
	int ret = 1;
	for(auto &elem:primes){
		const int tmp = power(val, phi / elem);
		if(tmp == 1){
			ret = lcm(ret, elem);
		}
	}
	return ret;
}

int ary[100010];

int main(void){

	int t;
	scanf("%ld %d", &p, &t);
	init();

	rep(loop, t){
		int k,a;
		scanf("%d", &k);
		rep(i, k) scanf("%d", ary +i);
		scanf("%d", &a);
		const ll goal = calc(a);
		const int all = p - 1;
		int period = p - 1;

		bool ok = false;
		rep(i, k){
			const ll idx = calc(ary[i]);
			period = gcd(period, idx);
		}

		if(goal % period == 0) ok = true;
		printf("%d\n", ok);
	}

	return 0;
}