#include<fstream>
#define nmax 1000000
#define mod 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
bool v[1000001];
int N, A, p[nmax/2], Nr;
int x = 0, y = 0, d = 0;
void ciur()
{
    v[0] = v[1] =true;

    for(int i = 2; i <= nmax; i++)
        if(v[i] == false)
            for(int j = i + i; j <= nmax; j +=i)
                v[j] = true;

    for(int i = 1; i <= nmax; i++ )
        if(v[i] == false)
            p[++Nr] = i;
}

void euclid(int a, int b, int &d, int &x, int &y)
{
    if(b == 0)
    {
       d = a;
       x = 1;
       y = 0;

    }
    else
    {
        int x0, y0;
        euclid(b, a%b, d, x0, y0 );
        x = y0;
        y = x0 - (a/b) * y0;
    }
}
int calc_invers(int z)
{
    x = 3423;
    euclid(z, mod, d, x, y);
    while( x < 0 )
        x += mod;
    return x % mod;
}

int rid(int f, int y)
{
    int aux = 1;
    for(int i = 1 ;  i <= y; i++ ,aux *= f);
    return aux;
}
int desc(int A)
{
    int d[100], nk[100];

    for(int i = 0; i <= 99; i++)
        d[i] = 0, nk[i] = 0;

    for(int i = 1; p[i] <= A ; i++)
        if(A % p[i] == 0)
        {
            d[++d[0]] = p[i];
            while(A % p[i] == 0)
                A /= p[i], nk[d[0]]++;
        }

    int Nr_div = 1 , S1 = 1, S2 = 1 ;

    for(int i = 1; i <= d[0]; i++)
        Nr_div *= (nk[i] + 1);

    for(int i = 1; i <= d[0] ; i++)
    {
        //int y = calc_invers(d[i] - 1);
        int w = rid(d[i], nk[i] + 1);
        --w;

        //fout <<w << " " <<d[i] <<'\n' ;
        //fout <<y<<'\n';
        S1 = (S1 * w) %mod;
        S2 = (S2 * (d[i] - 1)) %mod;
    }
    //int q = S2;
    int q = calc_invers(S2);
    fout << Nr_div <<" " << S1 * q % mod<<'\n';
}

void read()
{
    fin >> N;
    for(int i = 1; i <= N ;i++)
        fin >> A, desc(A);

}

int main()
{
    ciur();
    read();
    fin.close();
    return 0;
}