#include<fstream>
using namespace std;
ifstream fi("ssnd.in");
ofstream fo("ssnd.out");
int i,j,n,x,y,sol,t,p,p1,b,k,kk,e[1000001],vv[100000],a[100000];
char v[1000001];
double z,zz;
int put(int x,int n){
	int p=1;
	while(n!=0){
		if(n%2==1)
			p=((p%9973)*(x%9973))%9973;
		x=((x%9973)*(x%9973))%9973;
		n/=2;
	}
	return p;
}
int main(){
	fi>>t;
	for(i=2;i<=1000000;++i)
		if(!v[i]){
			for(j=2*i;j<=1000000;j+=i)
				v[j]=1;
			vv[++kk]=i;
		}
	
	for(int o=1;o<=t;++o){
		fi>>n;
		sol=1;
		zz=n;
		zz*=1.0;
		z=sqrt(zz);
		x=int (z);
		k=0;
		for(i=1;vv[i]<=x&&n>1;++i){
				y=1;
				e[vv[i]]=0;
				while(n%vv[i]==0){
					e[vv[i]]++;
					y+=1;
					n/=vv[i];
				}
				if(e[vv[i]])
					a[++k]=vv[i];
				
				sol*=y;
			}
		if(n>1){
			sol*=2;
			a[++k]=n;
			e[n]=1;
		}
		fo<<sol<<' ';
		sol=1;
		for(i=1;i<=k;++i){
			p=put(a[i],e[a[i]]+1)-1;
			b=a[i]-1;
			p1=put(b,9971);
			sol*=(p*p1)%9973;
		}
		fo<<sol<<'\n';
		
	}

	fo.close();
	fi.close();
	return 0;
}