1 //题解代码
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define LL long long
 5 #define LD long double
 6 #define ull unsigned long long
 7 const LL N=5e5+10;
 8 const LL INF=1e18;
 9 LL a,P,b;
10 int cnt=0;
11 void init(){
12     return;
13 }
14 
15 void add(LL &x,LL y){
16     x+=y;if(x>=P)x-=P;
17 }
18 
19 LL mul(LL x,LL y){
20     LL re=0;
21     while(y){
22         if(y&1) add(re,x);
23         add(x,x);y>>=1;
24     } 
25     return re;
26 }
27 
28 inline long long Mul(long long x,long long y){
29     long long tmp=(x*y-(long long)((long double)x/P*y+1.0e-8)*P);
30     return (tmp+P)%P;
31 }
32 
33 LL qpow(LL x,LL y){
34     LL re=1,re2;
35     while(y){
36         if(y&1) {
37             re=Mul(re,x);
38         }
39         x=Mul(x,x);
40         y>>=1;
41     }
42     return re;
43 }
44 
45 void MAIN(){
46     scanf("%lld%lld",&a,&P);
47     b=qpow(a,(P-1)/2);
48     if(b==1) {
49         puts("0");
50     }
51     else if(b==P-1) {
52         puts("1");
53     }
54     else{
55     //    cout<<a<<" "<<P<<" "<<b<<endl;
56         ++cnt;
57     }
58     return;
59 }
60 int main(){
61     freopen("1.in","r",stdin);
62     freopen("1.out","w",stdout);
63     init();
64     int ttt=1;scanf("%d",&ttt);
65     while(ttt--) MAIN();
66     //cout<<cnt<<endl;
67     return 0;
68 }
69 /*
70 
71 */
72