#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "ssnd";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

typedef long long int lld;
typedef pair<lld, int> PLI;
const int MOD = 9973;

int N, T;
lld X;
int P[100000], top;
bitset<50005> viz;
PLI Q[20];

void ciur() {
    int i, j;

    P[++top] = 2;

    for(i = 3; i * i <= 100000; i += 2)
        if(!viz[i / 2]) {
            P[++top] = i;
            for(j = i * i; j <= 100000; j += 2 * i)
                viz[j / 2] = 1;
        }

    for(; i <= 100000; i += 2)
        if(!viz[i / 2])
            P[++top] = i;
}

void desc(lld x, PLI *Q, int &T) {
    int i, p;

    for(i = 1; i <= top && P[i] * 1LL * P[i] <= x; i++)
        if(x % P[i] == 0) {
            p = 0;

            while(x % P[i] == 0) {
                p++;
                x /= P[i];
            }

            Q[++T] = make_pair(P[i], p);
        }

    if(x > 1)
        Q[++T] = make_pair(x, 1);
}

int expLog(int B, int E) {
    int i, ans = 1;

    for(i = E; i; i /= 2) {
        if(i & 1)
            ans = (ans * B) % MOD;
        B = (B * B) % MOD;
    }

    return ans;
}

int invMod(int x) {
    return expLog(x, MOD - 2);
}

int main() {
    int i, nrdiv, sum;

#ifndef ONLINE_JUDGE
    freopen(inputFile.c_str(), "r", stdin);
    freopen(outputFile.c_str(), "w", stdout);
#endif

    scanf("%d", &N);

    ciur();

    while(N--) {
        scanf("%lld", &X);

        T = 0;

        desc(X, Q, T);

        nrdiv = sum = 1;

        for(i = 1; i <= T; i++) {
            nrdiv *= (Q[i].second + 1);
            nrdiv %= MOD;
            sum *= (expLog(Q[i].first % MOD, Q[i].second + 1) - 1 + MOD) % MOD;
            sum %= MOD;
            sum *= invMod((Q[i].first - 1 + MOD) % MOD);
            sum %= MOD;
        }

        printf("%d %d\n", nrdiv, sum);
    }

    return 0;
}