#include <bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;
int t;ll p;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll phi(ll x)
{
	ll ans=x;
	for(int i=2;1ll*i*i<=x;++i)if(x%i==0)
	{
		ans=ans/i*(i-1);
		while(x%i==0)x/=i;
	}
	if(x!=1)ans=ans/x*(x-1);
	return ans;
}
map<ll,int> mp;
ll qpow(ll bs,ll ex){ll ans=1;while(ex){if(ex&1)ans=(lll)ans*bs%p;bs=(lll)bs*bs%p;ex>>=1;}return ans;}
int main()
{
	scanf("%d%lld",&t,&p);ll pi=phi(p),tpi=pi;//printf("pi:%lld\n",pi);
	for(int i=2;1ll*i*i<=pi;++i)
	{
		while(pi%i==0)++mp[i],pi/=i;
	}
	if(pi!=1)++mp[pi];
	pi=tpi;
	while(t--)
	{
		ll B;scanf("%lld",&B);
		if(gcd(B,p)!=1){printf("-1\n");continue;}
		ll res=pi;
		for(auto x:mp)
		{
			while(res%x.first==0&&qpow(B,res/x.first)==1)res/=x.first;
		}
		ll k;
		// ll ans=-1;
		// for(int k=1;k<=pi;++k)if(qpow(B,k+1)==p-1){ans=k;break;}
		// printf("%lld\n",ans);
		// printf("res:%lld\n",res);
		if(res%2==0&&qpow(B,res/2)==p-1)
		{
			if(res==2)printf("2\n"),k=2;
			else printf("%lld\n",res/2-1),k=res/2-1;
		}
		else printf("-1\n");
		// putchar(10);
	}
	fclose(stdin);fclose(stdout);return 0;
}