#include<fstream>
#include<math.h>
#include<bitset>
using namespace std;
ifstream fi("ssnd.in");
ofstream fo("ssnd.out");
int i,j,x,y,t,b,k,kk,e[101],vv[80000];
bitset <1000001> v;
double z,zz;
long long a[100],p,p1,sol,n;
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;
				while(n%vv[i]==0){
					y+=1;
					n/=vv[i];
				}
				if(y>1){
					a[++k]=vv[i];
					e[k]=y-1;
				}
				sol*=y;
			}
		if(n>1){
			sol*=2;
			a[++k]=n;
			e[k]=1;
		}
		fo<<sol<<' ';
		sol=1;
		for(i=1;i<=k;++i){
			p=put(a[i],e[i]+1)-1;
			b=a[i]-1;
			p1=put(b,9971);
			sol*=(p*p1)%9973;
			sol%=9973;
		}
		fo<<sol<<'\n';
		
	}

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