#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

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

const long long MOD = 9973;

vector<long long>primes;
bool c[1000005];

long long lgput(long long n, long long p)
{
	long long sol = 1;
	long long a = n;
	for (long long i = 0; (1ll << i) <= p; i++)
	{
		if ((1ll << i) & p)
			sol = (sol * a) % MOD;
		a = (a * a) % MOD;
	}
	return sol;
}

long long imod(long long n)
{
	return lgput(n, MOD - 2);
}

void ciur(int n)
{
	c[0] = c[1] = 1;
	for (int i = 4; i <= n; i += 2)
		c[i] = 1;
	int lim = (int)sqrt((double)n);
	for (int i = 3; i <= lim; i++)
		if (c[i] == 0)
			for (int j = i * i; j <= n; j += 2 * i)
				c[j] = 1;
}

void precalcPrimes(int n)
{
	ciur(n);
	for (int i = 1; i <= n; i++)
		if (c[i] == 0)
			primes.push_back(1ll*i);
}

long long answer(long long p, long long d)
{
	long long val1 = (lgput(p, d + 1)-1)%MOD;
	long long val2 = imod((p - 1));
	return (val1 * val2) % MOD;
}

pair<int, long long> getInfo(long long n)
{
	long long e = 0, k = 0;
	int cnt = 1;
	long long sum = 1;
	long long lim = (long long)sqrt((double)n);
	while (primes[k] <= lim)
	{
		long long d = primes[k];
		e = 0;
		while (n % d == 0)
		{
			e++;
			n /= d;
		}
		if (e > 0)
		{
			cnt = (cnt * (e + 1)) % MOD;
			sum = (sum * answer(d,e));
		}
		k++;
	}
	if (n > 1)
		return (make_pair(2, (n+1)%MOD));
	return make_pair(cnt, sum);
}

int main()
{
	precalcPrimes(1000000);
	int t;
	long long n;
	fin >> t;
	while (t--)
	{
		fin >> n;
		pair<int, long long>info = getInfo(n);
		fout << info.first << " " << info.second << "\n";
	}
	return 0;
}