#include <cstdio>
#define MOD 9973
#include <bitset>
 
using namespace std;
 
long long n,x,s;
long long a[80005],nr;
bitset <1000005> c;
 
void ciur()
{
    for(int i=2;i<=1000002;i++)
    {
        if(c[i]==0)
        {
            for(int j=i*2;j<=1000002;j+=i)
                c[j]=1;
            a[++a[0]]=i;
        }
    }
}
 
void cmmdc(long long x,long long y,long long &k,long long &l)
{
    if(y==0)
    {
        k=1;
        l=0;
        return;
    }
    long long k1,l1;
    cmmdc(y,x%y,k1,l1);
    k=l1;
    l=k1-(x/y)*l1;
}
 
long long inv(long long a)
{
    long long k,l;
    cmmdc(a,MOD,k,l);
    while(k<0)
    {
        k+=MOD;
    }
    return k;
}
 
long long put(long long n,long long p)
{
    long long rez=1;
    while(p!=0)
    {
        if(p%2 ==1)
        {
            p--;
            rez=(rez*n)%MOD;
        }
        p/=2;
        n=(n*n)%MOD;
    }
    return rez%MOD;
}
void diviz(long long x,long long &nr,long long &s)
{
    nr=1;s=0;
    long long ps=1,pj=1;
    for(int i=1;a[i]*a[i]<=x;i++)
    {
       int nrd=0;
       while(x%a[i]==0)
       {
           nrd++;
           x/=a[i];
       }
       if(nrd != 0)
        {
           nr*=(nrd+1);
           ps=(ps*(put(a[i],nrd+1)-1)%MOD);
           pj=(pj*a[i]-1)%MOD;
           
       }
   }
   s=(ps)%MOD;
   s=(s*inv(pj))%MOD;
   if(x!=1)
   {
       nr*=2;
       s=(s*(1+x)%MOD);
   }
}
 
int main()
{
    freopen("ssnd.in","r",stdin);
    freopen("ssnd.out","w",stdout);
 
    scanf("%lld",&n);
    ciur();
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        diviz(x,nr,s);
        printf("%lld %lld\n",nr,s);
    }
 
    return 0;
}