#include <bits/stdc++.h>
using namespace std;
//ifstream f("ssnd.in");
ofstream g("ssnd.out");
// #define f cin
// #define g cout
class InParser
{
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == 4096)
        {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char *nume)
    {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser &operator>>(int &n)
    {
        char c;
        while (!isdigit(c = read_ch()) && c != '-')
            ;
        int sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser &operator>>(long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-')
            ;
        long long sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
InParser f("ssnd.in");
typedef long long ll;
const int nmax = 1000004, mod = 9973;
int invmod(ll);
bool sieve[nmax];
void atkin();
vector<int> primes{2, 3}, pi;
void query(ll);
int32_t main()
{
    ios_base::sync_with_stdio(false);
    g.tie(nullptr);
    atkin();
    int q;
    f >> q;
    for (ll x; q; q--)
        f >> x, query(x);
    return 0;
}
void atkin()
{
    for (int x = 1; x * x < nmax; x++)
        for (int y = 1; y * y < nmax; y++)
        {
            ll n = 4 * x * x + y * y;
            if (n < nmax && (n % 12 == 1 || n % 12 == 5))
                sieve[n] ^= 1;
            n -= x * x;
            if (n < nmax && n % 12 == 7)
                sieve[n] ^= 1;
            n -= 2 * y * y;
            if (x > y && n < nmax && n % 12 == 11)
                sieve[n] ^= 1;
        }
    for (int i = 5; i * i < nmax; i++)
        if (sieve[i])
            for (int j = i * i; j < nmax; j += i * i)
                sieve[j] = 0;
    for (int i = 3; i < nmax; i += 2)
        if (sieve[i])
            primes.emplace_back(i);
    pi.resize(primes.size());
}
int invmod(ll x)
{
    ll a = (x % mod), b = mod - 2, p = 1;
    while (b)
    {
        if (b & 1ll)
            p = (1ll * p * a) % mod;
        a = (1ll * a * a) % mod;
        b >>= 1ll;
    }
    return p;
}
void query(ll x)
{
    ll tot = 1, sum = 1;
    for (int i = 0; i < (int)primes.size() && 1ll * primes[i] * primes[i] <= x; i++)
        if (x % primes[i] == 0)
        {
            ll t = 0, p = primes[i] % mod;
            while (x % primes[i] == 0)
                x /= primes[i], t++, p = (1ll * p * primes[i]) % mod;
            tot *= t + 1;
            p--;
            if (p < 0)
                p += mod;
            sum = (1ll * sum * p) % mod;
            if (!pi[i])
                pi[i] = invmod(primes[i] - 1);
            sum = (1ll * sum * pi[i]) % mod;
        }
    if (x != 1)
    {
        tot <<= 1;
        sum = (1ll * sum * (x + 1)) % mod;
    }
    g << tot << " " << sum << '\n';
}