ELHC

#include <bits/stdc++.h>

using namespace std;
ifstream fin("elhc.in");
ofstream fout("elhc.out");
int T, G, P, cnt;
int po(int b, int e, int M)
{
    if(e==0) return 1;
    else if(e%2==0)
    {
        int z = po(b,e/2,M);
        return (1LL*z*z)%M;
    }
    else return (1LL*b*po(b,e-1,M))%M;
}
int Factor(int nr)
{
    int d, p;
    while(nr%2==0)
    {
        p++;
        nr/=2;
    }
    if(p)
    {
        if(po(G,(P-1)/2, P)==1)
            return 1;
    }
    for(d=3; d*d<=nr; d+=2)
    {
        p=0;
        while(nr%d==0)
        {
            p++;
            nr/=d;
        }
        if(p)
        {
            if(po(G,(P-1)/d, P)==1)
                return 1;
        }
    }
    if(nr>1)
        if(po(G,(P-1)/nr, P)==1)
                return 1;
    return 0;
}
int main()
{
    fin>>T;
    for(int i=1; i<=T; ++i)
    {
        fin>>G>>P;
        if(G==1 && P==2)
            fout<<1;
        else
            fout<<!Factor(P-1);
    }
    return 0;
}