#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int a[1000001];
long long int b[1000001];
int c,k,t;

void ciur()
{
    int i,j,n;
    n=sqrt(1000000);
    for (i=1; i<=n; i++) a[i]=1;
    k=0;
    for (i=2; i<=1000000; i++)
       if (a[i])
       {
           j=i*2;
           while (j<=1000000)
           {
               a[j]=0;
               j=j+i;
           }
           k++;b[k]=i;
       }

}

long long calc(long long n)
{
    int i;
    long long int p,l,j,h;
    p=1; l=1;
    for (i=1; i<=k; i++)
    {
        if (n%b[i]==0)
        {
            j=1;h=0;
            while (n%b[i]==0)
            {
               j=j*b[i];
               n=n/b[i];
               h++;
            }
            j=j*b[i]-1; l=l*(b[i]-1); p=p*j; c=c*(h+1);
        }
        if (n==1) break;
    }
    return round(p/l);
}

void afis()
{
    int i;
    long long int p,x;
    freopen("ssnd.in","r",stdin);
    freopen("ssnd.out","w",stdout);
    scanf("%lld",&t);
    for (i=1; i<=t; i++)
    {
     scanf("%lld",&x);
     c=1;
     p=calc(x)%9973;
     printf("%i %lld",c,p);
    }
}

int main()
{
    ciur();
    afis();
    return 0;
}