#include<iostream>
#include<cstdio>
#define N 30
using namespace std;
long long read()
{
    char c=0;
    long long sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int T,length;
long long tong[N+1],b,p,phip;
long long fast_pow(long long a,long long b)
{
    long long res=1,mul=a;
    while (b)
    {
	if (b&1) res=(__int128)(res)*mul%p;
	mul=(__int128)(mul)*mul%p,b>>=1;
    }
    return res;
}
long long gcd(long long a,long long b)
{
    if (!b) return a;
    return gcd(b,a%b);
}
int main()
{
    long long x;
    T=read(),x=p=phip=read();
    for (long long i=2;i*i<=p;++i)
	if (x%i==0)
	{
	    phip=phip/i*(i-1);
	    while (x%i==0) x/=i;
	}
    if (x!=1) phip=phip/x*(x-1);
    x=phip;
    for (long long i=2;i*i<=phip;++i)
	if (x%i==0)
	{
	    tong[++length]=i;
	    while (x%i==0) x/=i;
	}
    if (x!=1) tong[++length]=x;
    while (T--)
    {
	b=read();
	if (gcd(p,b)!=1)
	{
	    puts("-1");
	    continue;
	}
	if (p==2)
	{
	    puts("1");
	    continue;
	}
	x=phip;
	for (int i=1;i<=length;++i)
	    while (x%tong[i]==0&&fast_pow(b,x/tong[i])==1)
		x/=tong[i];
	if (x&1) puts("-1");
	else
	{
	    if (x!=2) printf("%lld\n",(x-2)>>1);
	    else puts("2");
	}
    }
    return 0;
}