#include <fstream>
#define MOD 9973
#define ll long long
using namespace std;
ifstream f("ssnd.in");
ofstream g("ssnd.out");
bool ciur[1000010];
ll i,j,d,x,nr,sum,s,p,n,pp[100005],m;
ll putere(ll x,ll y)
{
    ll a;
    if(y==0)return 1;
    if(y==1)return x;
    a=putere(x,y/2);
    if(y%2==0)return (a*a)%MOD;
    if(y%2==1)return ((a*a)%MOD*x)%MOD;
}
int main()
{
     for(d=2;d*d<=1000000;d++)
        if(ciur[d]==0)
          {
          pp[++m]=d;
          for(i=d*d;i<=1000000;i=i+d)ciur[i]=1;
          }
    ciur[0]=1;
    ciur[1]=1;
     f>>n;
     sum=1;
     for(i=1;i<=n;i++)
     {
        f>>x;
        nr=1;
        sum=1;
        for(d=1;d<=m&&pp[d]*pp[d]<=x;d++)
        {
        if(x%pp[d]==0)
        {p=1;
        s=pp[d];
        while(x%pp[d]==0)
        {
        p++;
        s=(s*pp[d]);
        x=x/pp[d];
        }
        sum=(sum*(s-1)*(putere(pp[d]-1,MOD-2)))%MOD;
        nr=nr*p;
        }
        }
        if(x>1){sum=sum*((x*x-1)*(putere(x-1,MOD-2)))%MOD;nr=nr*2;
              }
       g<<nr<<" "<<sum<<'\n';
     }
    return 0;
}