#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

typedef long long lint;

struct stupit
{
    lint k, l;
};

const lint modit = 9973;
lint raiseit(lint a, int p){
    lint r = 1, q = a;
    while(p > 0){
        if(bool(p&1)){
            r *= q;
            r %= modit;
        }
        q *= q;
        a %= modit;
        p >>= 1;
    }
    return r;
}

bool frecu[1000041];
vector<int> primes;
void primeit()
{
    for(int i = 2; i <= 1000000; i++)
    {
        if(!frecu[i])
        {
            primes.push_back(i);
            for(int j = i+i; j <= 1000000; j += i)
            {
                frecu[j] = true;
            }
        }
    }
}

stupit verseit(lint a, lint b)
{
    if(b == 0)
    {
        return {1, 0};
    }
    stupit pr = verseit(b, a%b);
    return {pr.l, pr.k-pr.l*(a/b)};
}

int inverseit(lint a)
{
    return (verseit(a, modit).k + modit) % modit;
}

int n;
void solveit()
{
    lint a;
    fin >> a;
    lint cer = 1, sol = 1;
    for(int i = 0; i < primes.size() && a != 1; i++)
    {
        lint p = primes[i], c = 1;
        while(a % p == 0)
        {
            a /= p;
            c++;
        }
        lint q = raiseit(p, c);
        if(c > 1)
        {
            sol *= (q-1);
            sol *= inverseit(p-1);
            sol %= modit;
            cer *= c;
        }
    }
    if(a != 1)
    {
        lint b = a;
        b %= modit;
        b *= a;
        b %= modit;
        b = b-1+modit;
        b %= modit;
        sol *= b;
        sol *= inverseit(a-1);
        sol %= modit;
        cer *= 2;
    }
    fout << cer << " " << sol << "\n";
}

int main()
{
    primeit();
    fin >> n;
    for(int i = 0; i < n; i++)
    {
        solveit();
    }
}