program math;
Const
maxn=100000;
maxm=2;
StrErr='Orz, I cannot find x!';
Type
rec=record
val,ord:longint;
end;
var
p,q,n,m,op,gcd:int64;
i:longint;
t:array[0..maxn,0..maxm] of rec;
Function safe(P:int64):int64;inline;
begin
exit(((p+n) mod n+n) mod n);
end;
Function times(p,q:int64):int64;//P^Q (mod N)
begin
if q=0 then exit(1);
times:=times(p,q shr 1);
times:=safe(times*times);
if odd(q) then times:=safe(times*p);
end;
Procedure Exgcd(a,b:int64;var x,y:int64);
begin
if b=0 then begin x:=1;y:=0;gcd:=a;exit; end;
Exgcd(b,a mod b,y,x);
y:=safe(y-a div b*x);
end;
Procedure Solve1;inline;//pX+Yn=Q
var
x,y:int64;
begin
Exgcd(p,n,x,y);
if q mod gcd<>0 then begin writeln(StrErr); exit; end;
x:=safe(x);
writeln(safe((q div gcd)*x));
end;
Procedure Addhash(val,ord:int64); inline;
var
hash,i:longint;
begin
hash:=(val mod maxn+maxn) mod maxn;
//writeln('addhash ',val,' ',ord);
for i:=1 to maxm do
begin
if t[hash,i].ord>0 then continue;
t[hash,i].ord:=ord;
t[hash,i].val:=val;
break;
end;
end;
Function InHash(P:longint;var pos1,pos2:int64):boolean;inline;
var
hash,i:longint;
begin
hash:=(p mod maxn+maxn) mod maxn;
for i:=1 to maxm do
begin
if t[hash,i].ord=0 then break;
if t[hash,i].val=p then
begin
pos1:=hash;
pos2:=i;
exit(true);
end;
end;
exit(false);
end;
Function inv(P:int64):int64;inline;//pX=1 (mod n)
var
x,y:int64;
begin
Exgcd(p,n,x,y);
if gcd=1 then exit((x+n) mod n) else exit(-1);
end;
Procedure Solve2;inline;//P^x=q (mod n)
var
size,v,now,pos1,pos2:int64;
i:longint;
begin
q:=q mod n;
size:=trunc(sqrt(n))+1;
fillchar(t,sizeof(t),0);
v:=inv(times(p,size));
now:=1;
for i:=1 to size do
begin
now:=(now*p) mod n;
Addhash(now,i);
end;
//for i:=0 to n-1 do for j:=1 to 3 do writeln('hash=',i,' num=',j,' ',t[i,j].ord,' ',t[i,j].val);
For i:=0 to size-1 do
begin
if inhash(q,pos1,pos2) then
begin
writeln((size*i+t[pos1,pos2].ord) mod n);
exit;
end;
q:=(q*v) mod n;
end;
Writeln(strErr);
end;
begin
readln(m,op);
for i:=1 to m do
begin
readln(p,q,n);
case op of
1:writeln(times(p,q));
2:solve1;
3:solve2;
end;
end;
end.