#include<stdio.h>
#include<string.h>
#define Ld 1000000
#define MOD 9973
#define divizori 80000
using namespace std;
int t,T,i,n,prim[divizori],ciur[Ld+1],P,d[divizori],D,exp[divizori],Nr,Sum;


void precalc()
{
	int i,j;
	
	for(i=2;i<=Ld;i++)
		if(!ciur[i])
		{
			prim[++P]=i;
			for(j=i+i;j<=Ld;j+=i)
				ciur[j]=1;
		}
}

int lgput (int a, int b)
{
	int S;
	
	for(S=1;b;a=(a*a)%MOD,b>>=1)
		if(b&1) S=(S*a)%MOD;
	
	return S;
}

int main()
{
	freopen("ssnd.in","r",stdin);
	freopen("ssnd.out","w",stdout);
	
	scanf("%d",&T);
	
	precalc();
	
	for(t=1;t<=T;t++)
	{
		scanf("%d",&n);
		
		D=0;
		for(i=1; i<=P && prim[i] <= n; i++)
			if(n%prim[i]==0)
			{
				d[++D]=prim[i];
				exp[D]=1;
				while(n%prim[i]==0)
				{
					exp[D]++;
					n/=prim[i];
				}
			}
		if(n!=1) { d[++D]=n; exp[D]=2;}
		Nr=1;
		for(i=1;i<=D;i++)
			Nr*=exp[i];
		
		Sum=1;
		for(i=1;i<=D;i++)
			Sum=(Sum * (lgput(d[i],exp[i])-1)/(d[i]-1) ) % MOD;
		
		printf("%d %d\n",Nr,Sum);
	}
	return 0;
}