var     t,i,j,k,l:longint;
        n:int64;
        a,b:array[1..100000000] of longint;
        f,g:text;

begin
  assign(f,'ssnd.in');
  assign(g,'ssnd.out');
  reset(f);
  rewrite(g);
  readln(f,t);
  readln(f,n);
  for i:=2 to t do
    begin
      readln(f,k);
      if k>n then n:=k;
    end;
  reset(f);
  readln(f);
  for i:=1 to n div 2 do
    begin
      j:=i;
      while j<=n do
        begin
          inc(a[j]);
          b[j]:=b[j]+i;
          if b[j]>2000000000 then b[j]:=b[j] mod 9973;
          inc(j,i);
        end;
    end;

  for l:=1 to t do
    begin
      readln(f,n);
      writeln(g,a[n]+1,' ',(b[n]+n) mod 9973);
    end;
  close(g);
end.