{$N+,E-}
program tmp2;
{$APPTYPE CONSOLE}
uses
  SysUtils;
var i,k,j,p,q,d:integer;
    n,e,c:int64;
function pow1(a,k:int64):int64;
var b:int64;
begin
  b:=1;
  while k>0 do
      if k mod 2 = 0 then
        begin
          k:=k div 2;
          a:=a*a;
        end
      else
        begin
          dec(k);
          b:=b*a;
        end;
  pow1:=b;
end;
function powmod(a,k,n:int64):int64;
var b:int64;
begin
  b:=1;
  while k>0 do
    if k mod 2 = 0 then
      begin
        k:=k div 2;
        a:=(a*a) mod n;
      end
    else
      begin
        dec(k);
        b:=(b*a) mod n;
      end;
  powmod:=b;
end;
procedure factor(n:integer);
var d:integer;
begin
  for d:=2 to trunc(sqrt(n)) do
    if n mod d =0 then
      begin
        p:=d;
        q:=n div d;
        exit;
      end;
end;
begin
  { TODO -oUser -cConsole Main : Insert code here }
{  reset(input,'data.in');
  rewrite(output,'data.out');}
  readln(k);
  for i:=1 to k do
    begin
      readln(e,n,c);
      factor(n);
      d:=1;
      while (1+k*(p-1)*(q-1)) mod e <> 0 do inc(k);
      d:=(1+k*(p-1)*(q-1)) div e;
      writeln(powmod(c,d,n));
    end;
end.