记录编号	128991	评测结果	AAAAAAAAAA
题目名称	drei	最终得分	100
用户昵称	东方老败	是否通过	通过
代码语言	Pascal	运行时间	0.053 s
提交时间	2014-10-18 20:56:17	内存使用	0.27 MiB

var i,j,k,t,tot:longint;
    bo:array[1..32000]of boolean;
	pri:array[1..10000]of longint;
	yue:array[0..10000]of longint;
    a,x,p,phi:int64;

procedure deal;
begin
for i:=2 to 32000 do
begin
 if not bo[i] then
 begin
  inc(tot);pri[tot]:=i; //writeln(tot,' ',i);
 end;
 for j:=1 to tot do
 begin
  if i*pri[j]>32000 then break;
  bo[i*pri[j]]:=true;
  if i mod pri[j]=0 then break;
 end;
end;
end;

procedure get_phi(x:longint);
var i,j,k:longint;
begin
phi:=x;
for i:=1 to tot do
begin
if x mod pri[i]=0 then
    phi:=phi div pri[i] *(pri[i]-1);
while x mod pri[i]=0 do x:=x div pri[i];
if x=1 then break;
end;
if x<>1 then phi:=phi div x *(x-1);
end;

function qsm(x,y:int64):int64;
var ans:int64;
begin
ans:=1;
while y>0 do begin
if y and 1<>0 then ans:=(ans*x)mod p;
x:=(x*x)mod p;
y:=y>>1;
end;
exit(ans);
end;

function gcd(x,y:longint):longint;
begin
if y=0 then exit(x);
exit(gcd(y,x mod y));
end;

procedure work;
var i,o1:longint;k:int64;
begin
readln(a,p);
if ((gcd(a,p)<>1)and(a<>1)) or (p=1) then
 begin writeln(-1);exit;end;

get_phi(p);a:=a mod p;
k:=1;yue[0]:=0;o1:=0;
for i:=1 to trunc(sqrt(phi)) do
if phi mod i=0 then
begin
 inc(yue[0]);yue[yue[0]]:=i;
 k:=(k*qsm(a,i-o1))mod p;
 o1:=i;
 if k mod p=1 then
     begin writeln(i);exit;end;
end;

for i:=yue[0] downto 1 do
begin
 k:=(k*qsm(a,phi div yue[i]-o1))mod p;
 o1:=phi div yue[i];
 if k mod p=1 then
    begin writeln(phi div yue[i]);exit;end;
end;
end;

begin
assign(input,'drei.in');reset(input);
assign(output,'drei.out');rewrite(output);
deal;
readln(t);
for i:=1 to t do work;
close(input);close(output);
end.