Program cog1428;
Label
1;
Var
I,J,N,E,Phi:Longint;
A,M,P,T:Int64;
V:Array[1..31607]Of Longint;
Pr:Array[1..3401]Of Longint;
Function Gcd(A,B:Int64):Int64;
Begin
If B=0 Then Exit(A);
Exit(Gcd(B,A Mod B));
End;
Function Qe(A,B:Int64):Int64;
Var
S:Int64;
Begin
S:=1;
While B>0 Do
Begin
If B And 1=1 Then S:=S*A Mod M;
A:=A*A Mod M;
B:=B Shr 1;
End;
Exit(S);
End;
Begin
Assign(Input,'drei.in');
Assign(Output,'drei.out');
Reset(Input);
Rewrite(Output);
Fillchar(V,Sizeof(V),0);
N:=0;
For I:=2 To 31607 Do
Begin
If V[I]=0 Then
Begin
V[I]:=I;
Inc(N);
Pr[N]:=I;
End;
J:=1;
While (J<=N) And (Pr[J]<=V[I]) And (Pr[J]*I<=31607) Do
Begin
V[Pr[J]*I]:=Pr[J];
Inc(J);
End;
End;
Readln(N);
Repeat
Readln(A,P);
If (P=1) Or (P=0) Or (A=0) Or (Gcd(A,P)<>1) Then
Begin
Writeln(-1);
Goto 1;
End;
A:=A Mod P;
If A=1 Then
Begin
Writeln(1);
Goto 1;
End;
M:=P;
Phi:=P;
For I:=1 To 3401 Do
If P Mod Pr[I]=0 Then
Begin
Phi:=Phi Div Pr[I]*(Pr[I]-1);
While P Mod Pr[I]=0 Do P:=P Div Pr[I];
If P=1 Then Break;
End;
If P<>1 Then Phi:=Phi Div P*(P-1);
T:=Phi;
For I:=1 To 3401 Do
Begin
E:=Phi Div Pr[I];
If Phi<>E*Pr[I] Then Continue;
While (Phi=E*Pr[I]) And (Qe(A,E)=1) Do
Begin
Phi:=E;
E:=Phi Div Pr[I];
T:=T Div Pr[I];
End;
While T Mod Pr[I]=0 Do T:=T Div Pr[I];
End;
If (T<>1) And (Qe(A,Phi Div T)=1) Then Phi:=Phi Div T;
Writeln(Phi);
1:
Dec(N);
Until N=0;
Close(Input);
Close(Output);
End.
Ezoi_XY