# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
ll Phi(ll n)
{
	ll ans=n;
	for(ll i=2;i*i<=n;i++)
		if(n%i==0)
		{
			ans=ans/i*(i-1);
			for(;n%i==0;n/=i);
		}
	if(n>1) ans=ans/n*(n-1);
	return ans;
}
ll power(ll a,ll b,ll p)
{
	ll ans=1;
	for(;b;b>>=1,a=(lll)a*a%p)
		if(b&1) ans=(lll)ans*a%p;
	return ans;
}
int tot;
ll p,phi,pr[60],cnt[60];
ll Ord(ll n)
{
	ll ans=1;
	for(int i=1;i<=tot;i++)
	{
		ll cur=phi;
		for(int j=0;j<cnt[i];j++) cur/=pr[i];
		ll pw=power(n,cur,p);
		for(;pw>1;pw=power(pw,pr[i],p)) ans*=pr[i];
	}
	return ans;
}
int main()
{
	int T;
	cin>>T>>p;
	ll t=phi=Phi(p);
	for(ll i=2;i*i<=t;i++)
		if(t%i==0)
		{
			pr[++tot]=i;
			for(;t%i==0;t/=i) cnt[tot]++;
		}
	if(t>1) pr[++tot]=t,cnt[tot]=1;
	while(T--)
	{
		ll b;
		scanf("%lld",&b);
		if(__gcd(p,b)>1){puts("-1");continue;}
		if(p==2){puts("1");continue;}
		ll ord=Ord(b),ans;
		if(ord&1){puts("-1");continue;}
		ans=ord/2;
		if(ans<=1) ans+=ord;
		printf("%lld\n",ans-1);
	}
	return 0;
}