#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int cnt;
long long mul(long long A, long long B, long long P){
	long long C = A * B - (long long)((double)A * B / P + 0.1) * P;
	return C < 0 ? C + P : C;
}
ll pr[105];
ll qpow(ll x, ll y, ll z)
{
	ll ans = 1;
	while(y)
	{
		if(y & 1)
			ans = mul(ans, x, z)
		x = mul(x, x, z);
		y >>= 1;
	}
	return ans;
}
ll gcd(ll x, ll y)
{
	return x ? gcd(y % x, x) : y;
}
ll work(ll p)
{
	int i;
	ll q = p;
	cnt = 0;
	for(i = 2; i * i <= p; i++)
		if(!(p % i))
		{
			q -= q / i;
			pr[++cnt] = i;
			while(!(p % i))
				p /= i;
		}
	if(p > 1)
	{
		q -= q / p;
		pr[++cnt] = p;
	}
	return q;
}

int main()
{
	int T, i;
	ll p, q, r, b;
	scanf("%d%lld", &T, &p);
	work(q = work(p));
	while(T--)
	{
		scanf("%lld", &b);
		if(gcd(p, b) != 1)
		{
			printf("-1\n");
			continue;
		}
		if(p == 2)
		{
			printf("1\n");
			continue;
		}
		r = q;
		for(i = 1; i <= cnt; i++)
			while(!(r % pr[i]) && qpow(b, r / pr[i], p) == 1)
				r /= pr[i];
		if(r & 1)
		{
			printf("-1\n");
			continue;
		}
		r /= 2;
		if(qpow(b, r, p) == p - 1)
			printf("%lld\n", r - 1 + ((r == 1) << 1));
		else
			printf("-1\n");
	}
	return 0;
}

answer.code: In function ‘ll qpow(ll, ll, ll)’:
answer.code:18:45: error: expected ‘;’ before ‘x’
   18 |                         ans = mul(ans, x, z)
      |                                             ^
      |                                             ;
   19 |                 x = mul(x, x, z);
      |                 ~                            
answer.code: In function ‘int main()’:
answer.code:53:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |         scanf("%d%lld", &T, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
answer.code:57:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |                 scanf("%lld", &b);
      |                 ~~~~~^~~~~~~~~~~~