#include<fstream>
using namespace std;
long long t,b,nr,nrdiv,suma,aux,x,prim[1000010],pute1,i,aux1,j;
bool ok,ch[1000010];
double crer;
void ciur() { 
	prim[0]=2; nr=0;  
	for(i=1;i<=500000;i++)  { 
		if(!ch[i]) 
		{ 
			prim[++nr]=2*i+1; 
			for(j=2*i*i+2*i;j<=1000000;j+=2*i+1) 
				ch[j]=true; 
		}
	} 
} 
long long putere(int r,int s) { 
	if (s==0) return 1; 
	if (s%2==0) { 
		 aux=putere(r,s/2); 
		return (aux*aux); 
	} 
	if (s%2==1) return (r*putere(r,s-1)); 
} 
int main(){
	ifstream f("ssnd.in");
	ofstream g("ssnd.out");
	f>>t; 
	ciur();
	for (i=1;i<=t;i++){
		f>>b;
		nr=-1;nrdiv=1;aux1=b;ok=true;suma=1;
		while (b!=1){
			nr++;
			if (b%prim[nr]==0)
				while (b%prim[nr]==0){
					x++;
					b=b/prim[nr];
				}
			if(b>1 && putere(prim[nr],2)>aux1)  {                   
				ok=false;
				g<<"2"<<" ";    
			    g<<(aux1+1)%9973<<"\n";
				b=1;
			}
		if (ok==true){
			nrdiv=nrdiv*(x+1);
			pute1 = ((putere(prim[nr], x+1) - 1) % 9973)/(prim[nr]-1); 
			suma=(suma*pute1)%9973;
			x=0;
		}
		}
		if (ok==true)
			g<<nrdiv<<" "<<suma<<"\n";
	}
	return 0;
}