#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;

ifstream in("ssnd.in");
ofstream out("ssnd.out");

const int mod = 9973;
const int TMax = 1e3 + 5;
const int PMax = 1e6 + 15;
const long long valMax = 1e12 + 5;

long long T,N,nrPrimes;
long long v[TMax];
bool notPrime[PMax];
long long primes[PMax];

void ciur(long long);
long long getPhi(long long);
long long pw(long long,long long);
// ciur(N) - determina primele numere prime mai mici sau egale cu radical din N
// getPhi(N) - return-eaza numarul de numere mai mici sau egale cu N care au cmmdc(nr,N) = 1 (indicatorul lui Euler)
// pw(b,e) - return-eaza (b^e) % mod;

int main() {
    in>>T;

    long long totient = getPhi(mod);

    for (int i=1;i<=T;++i) {
        in>>v[i];
    }

    ciur(valMax);

    for (int cont=1;cont<=T;++cont) {
        N = v[cont];

        long long nrDiv = 1,sumTop = 1,sumBot = 1;

        for (long long i=1; primes[i]!=0 && primes[i]*primes[i]<=N ;++i) {
            long long p = primes[i];
            //cout<<p<<'\n';

            if (N % p == 0) {
                long long d = 0;
                while (N % p == 0) {
                    N /= p;
                    ++d;
                }
                nrDiv *= (d+1);

                sumTop = (sumTop * (pw(p,d+1) - 1 + mod)) % mod;
                sumBot = (sumBot * (p - 1)) % mod;
            }
        }
        if (N != 1) {
            nrDiv *= 2;
            sumTop = (sumTop * (pw(N,2) - 1 + mod)) % mod;
            sumBot = (sumBot * (N - 1)) % mod;
        }

        out<<nrDiv<<' '<<(sumTop * pw(sumBot,totient-1)) % mod<<'\n';
    }
    in.close();out.close();
    return 0;
}

void ciur(long long x) {
    long long lim = 1LL*sqrt(x) + 10;

    primes[++nrPrimes] = 2;
    for (int i=3;i<=lim;i+=2) {
        if (!notPrime[i]) {
            primes[++nrPrimes] = i;
            for (int j=3*i;j<=lim;j+=2*i) {
                notPrime[j] = true;
            }
        }
    }
}

long long getPhi(long long x) {

    long long phi = x;

    for (long long i=2; i*i <= x;++i) {
        if (x % i == 0) {
            while (x % i == 0) {
                x /= i;
            }
            phi = phi * (i-1) / i;
        }
    }
    if (x != 1) {
        phi = phi * (x-1) / x;
    }
    return phi;
}

long long pw(long long x,long long e) {
    long long prod = 1;

    while (e) {
        if (e%2 == 1) {
            prod = (prod * x) % mod;
        }
        x = (x*x) % mod;
        e >>= 1;
    }

    return prod;
}