#include "stdio.h"
#include "math.h"

bool p[1001001];
long prim[80000];
long long sz[1010];
int e=0;
long long x;
int nr;
int mnr=1;
int snr=1;
int y;
int i;
int n,z;
int j;
int kezd=2;
int vege=2;
long long max;
int ppw(long long a, long long x)
{
	if(x==1)return a%9973;
	int c=ppw(a, x/2);
	if(x%2)return (((c*c)%9973)*a)%9973;
	return (c*c)%9973;
}

void gen(int k, int v)
{
	for(i=k;i<=v+1;i++)
	{
		for(j=2;j*i<=v+1;j++)
			p[i*j]=1;
		if(p[i-1]==0)
			prim[e++]=i-1;
	}
}

int main()
{
	
	freopen("ssnd.in","r",stdin);
	freopen("ssnd.out","w",stdout);
	scanf("%d",&n);
	for(z=1;z<=n;z++)
	{
		scanf("%lld",&sz[z]);
		if(sz[z]>max)max=sz[z];
	}
	gen(2,sqrtl(max)+1);
	for(z=1;z<=n;z++)
	{
		x=sz[z];
		mnr=1;
		snr=1;
		for(j=1;j<e&&x>1;j++)
		{
			i=prim[j];
			nr=0;
			if(!(x%i))
			{
				while(!(x%i))
				{
					nr++;
					x/=i;
				}
			nr++;
			}
			if(nr)
			{
			mnr=( ((mnr*(ppw(i%9973, nr)-1))%9973) * ppw((i-1)%9973,9971) )%9973;
			snr=(snr*nr)%9973;
			}
		}
		if(x>1)
		{
			snr=(snr*2)%9973;
			mnr=( ((mnr*(ppw(x%9973, 2)-1))%9973) * ppw((x-1)%9973,9971) )%9973;
		}
			printf("%d %d\n",snr, mnr);
	}
	return 0;
}