#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>

using namespace std;

#define MOD 9973
#define MAX 1000000

int P[MAX], E[MAX], T, N, K, X;
vector <int> V;
bitset <MAX> B;

int s_div (int), pow (int, int);
void ciur (), descompunere (int);

int main () {
	
	freopen ("ssnd.in", "r", stdin);
	freopen ("ssnd.out", "w", stdout);
	
	ciur ();
	
	scanf ("%d", &T);
	
	for ( ; T; T--) {
		scanf ("%d", &N);
		
		descompunere (N);
		
		printf ("%d %d\n", X, s_div (N));
	}
	
	return 0;
}

int pow (int a, int exp) {
	
	int sol = 1; int p = a;
	for ( ; exp; exp >>= 1) {
		if (exp & 1)
			sol = (sol * p) % MOD;
		
		p = (p * p) % MOD;
	}
	
	return sol;
}

int s_div (int N) {
	
	int S = 1;
	for (vector <int>::iterator it = V.begin (); it != V.end (); it++) {
		int Y = pow (P[*it], E[*it] + 1) - 1;
		if (Y < 0) Y += MOD;
		S = (S * Y) % MOD;
		
		Y = pow (P[*it] - 1, MOD - 2);
		S = (S * Y) % MOD;
	}
	
	return S;
}

void ciur () {
	
	int i, j;
	for (i = 2; i <= MAX; i++)
		if (!B[i]) {
			P[++K] = i;
			for (j = 2 * i; j <= MAX; j += i)
				B[j] = 1;
		}
}

void descompunere (int N) {
	
	memset (E, 0, sizeof (E)); V.clear ();
	
	int M = N; int i; X = 1;
	for (i = 1; i <= K && P[i] * P[i] <= N; i++) {
		while (M % P[i] == 0) {
			if (!E[i]) V.push_back (i);
			E[i]++;
			M /= P[i];
		}
		if (E[i]) X = (X * (E[i] + 1)) % MOD;
	}
	
	if (M > 1) {
		for ( ; i <= K; i++)
			if (P[i] == M) break;
		E[i]++; V.push_back (i);
		X = (X * (E[i] + 1)) % MOD;
	}
}