program suma_dv_nr;
var t:integer;
    n,i,s,k:longint;
    p:array[1..1000005] of boolean;
    x:array[1..1000005] of longint;
procedure ciur;
const nmax=1000005;
var i,j:longint;
begin
for i:=2 to nmax do
         if not p[i] then
                     begin
                     j:=i+i; k:=k+1; x[k]:=i;
                     while j<nmax do begin
                                     p[j]:=true;
                                     j:=j+i;
                                     end;
                     end;
end;

procedure solve(n:longint);
const md=9973;
var i,nr,d,s1,y:longint;
    s:int64;

function putere(a,b:longint):int64;
var i:longint;
begin
putere:=a;
for i:=2 to b do putere:=(putere*a);
end;

begin
nr:=1;s:=1;s1:=1;i:=1;d:=0;y:=trunc(sqrt(n));
while x[i]<=y do
                if n mod x[i]=0 then begin
                                     n:=n div x[i];
                                     d:=d+1;
                                     end
                                else begin
                                     if d>0 then
                                            begin
                                            nr:=nr*(d+1);
                                            s:=(s*(putere(x[i],d+1)-1));
                                            s1:=(s1*(x[i]-1));
                                            d:=0;
                                            end;
                                     i:=i+1;
                                     end;
if (n>1)and(not p[n]) then begin
                           nr:=nr*2;
                           s:=(s*(putere(n,2)-1));
                           s1:=(s1*(n-1));
                           end;
s:=(s div s1) mod md;
writeln(nr,' ',s);
end;

begin
ciur;
assign(input,'ssnd.in'); reset(input);
assign(output,'ssnd.out'); rewrite(output);
readln(t);
for k:=1 to t do begin
                 readln(n);
                 solve(n);
                 end;
close(output);
end.