#include<stdio.h>
#include<bitset>

#define mod 9973
#define maxt 1005
#define maxsqrt 1000005
#define maxprimes 80000

using namespace std;

FILE*f=fopen("ssnd.in","r");
FILE*g=fopen("ssnd.out","w");

int q,nrp;
int Pr[maxprimes];
long long Q[maxt];
bitset<maxsqrt>neprim;

inline void ciur ( long long n ){
	
	for ( int i = 2 ; 1LL * i * i <= n ; ++i ){
		if ( !neprim[i] ){
			Pr[++nrp] = i;
			for ( int j = i + i ; 1LL * j * j <= n ; j += i ){
				neprim[j] = 1;
			}
		}
	}
}

inline int lgpow ( long long a , int b ){
	int s = 1, p = a % mod;
	
	while ( b ){
		if ( b & 1 ){
			s = (s * p) % mod;
		}
		p = (p * p) % mod;
		b = b >> 1;
	}
	
	return s;
}

inline void solve ( long long N , int &nr , int &s ){
	int i;
	
	for ( i = 1 ; 1LL*Pr[i]*Pr[i] <= N && N > 1 && i <= nrp ; ++i ){
		if ( !(N % Pr[i]) ){
			int p = 0; int prod = Pr[i];
			while ( !(N % Pr[i]) ){
				N /= Pr[i];
				++p; prod = (1LL * prod * Pr[i]) % mod;
			}
			nr = (nr * (p + 1)) % mod;
			--prod; if ( prod < 0 )	prod = mod - 1;
			s = (1LL * s * prod * lgpow(Pr[i]-1,mod-2)) % mod;
		}
	}
	
	if ( N > 1 ){
		nr = nr + nr; if ( nr >= mod )	nr -= mod;
		s = (((1LL*s * (N * N - 1)) % mod) * lgpow(N-1,mod-2)) % mod;
	}
}

int main () {
	
	fscanf(f,"%d",&q);
	
	long long val_max = 0;
	for ( int i = 1; i <= q ; ++i ){
		fscanf(f,"%lld",&Q[i]);
		if ( Q[i] > val_max ){
			val_max = Q[i];
		}
	}
	
	ciur(val_max);
	
	for ( int i = 1 ; i <= q ; ++i ){
		int nr = 1,s = 1;
		solve(Q[i],nr,s);
		fprintf(g,"%d %d\n",nr,s);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;	
}