#include <cstdio>
#define MOD 9973

using namespace std;

int n,x,a[100000],nr,s;
char c[1000005];

void ciur()
{
    for(int i=2;i<=1000005;i++)
    {
        if(c[i]==0)
        {
            for(int j=i*2;j<=1000005;j+=i)
                c[j]=0;
            a[++a[0]]=i;
        }
    }
}

void cmmdc(int x,int y,int &k,int &l)
{
    if(y==0)
    {
        k=1;
        l=0;
        return;
    }
    int k1,l1;
    cmmdc(y,x%y,k1,l1);
    k=l1;
    l=k1-(x/y)*l1;
}

int inv(int a)
{
    int k,l;
    cmmdc(a,MOD,k,l);
    while(k<0)
    {
        k+=MOD;
    }
    return k;
}

int put(int n,int p)
{
    int 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(int x,int &nr,int &s)
{
    nr=1;s=0;
    int 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];
       }
       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("%d",&n);
    ciur();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        diviz(x,nr,s);
        printf("%d %d\n",nr,s);
    }

    return 0;
}