#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;
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);
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);
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';
}