#include <bits/stdc++.h>
using namespace std;
ifstream f("ssnd.in");
ofstream g("ssnd.out");
// #define f cin
// #define g cout
typedef long long ll;
const int nmax = 1000004, mod = 9973;
bool sieve[nmax];
void atkin();
vector<int> primes{2, 3};
void query(ll);
int32_t main()
{
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    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);
}
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, r = 1;
            while (x % primes[i] == 0)
                x /= primes[i], t++, r += p, p = (1ll * p * primes[i]) % mod, r %= mod;
            tot *= t + 1;

            sum = (1ll * sum * r) % mod;
        }
    if (x != 1)
    {
        tot <<= 1;
        sum = (1ll * sum * (x + 1)) % mod;
    }
    g << tot << " " << sum << '\n';
}