#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v = a; v <= b; v++)
#define fr(v,a,b) for(int v = a; v >= b; v--)
#define cl(a,v) memset(a, v, sizeof(a))

typedef long long ll;

ll mul(ll A, ll B, ll P){
	ll C = A * B - (ll)((double)A * B / P + 0.1) * P;
	return C < 0 ? C + P : C;
}
ll power(ll a, ll x, ll P) {
    ll res = 1;
    while(x) {
        if(x & 1LL) res = mul(res, a, P);
        a = mul(a, a, P), x >>= 1;
    } return res;
}

const int N = 110;

ll pr[N]; int q[N], cc;

void Divide(ll P) {
    cc = 0, cl(pr, 0), cl(q, 0);
    for(int i = 2; (ll)i * i <= P; i++)
        if(P % i == 0) {
            cc++, pr[cc] = i;
            while(P % i == 0) P /= i, q[cc]++;
        }
    if(P > 1) pr[++cc] = P, q[cc] = 1;
}

ll b, P, phiP, ans;

void Main() {
    scanf("%lld", &b), b %= P;
    if(__gcd(b, P) != 1) return puts("-1"), void();

    ans = phiP;
    fo(i, 1, cc) {
        while(ans % pr[i] == 0) {
            if(power(b, ans / pr[i], P) == 1)
                ans /= pr[i];
            else break;
        }
    }
    if(ans & 1) return puts("-1"), void();
    ll d = ans / 2;
    if(power(b, d, P) != P - 1) return puts("-1"), void();
    ll res = d - 1; if(res == 0) res += ans;
    printf("%lld\n", res);
}

int main()
{
    int T; scanf("%d%lld", &T, &P);

    Divide(P), phiP = 1;
    fo(i, 1, cc) {
        phiP *= pr[i] - 1;
        fo(j, 2, q[i]) phiP *= pr[i];
    }
    Divide(phiP);

    while(T--) Main();

    return 0;
}
/*
 
*/