#include<stdio.h>
#define mod 9973
FILE*f=fopen("ssnd.in","r");
FILE*g=fopen("ssnd.out","w");
long long n;
int nr,v[80000],t;
char c[1000001];
struct div
{
	int e;
	long long p;
} w[50001];
int put(int x,int e)
{
	int p=1;
	while(e)
	{
		if(e%2)
			p=(p%mod)*(x%mod)%mod;
		x=(x%mod)*(x%mod)%mod;
		e/=2;
	}
	return p;
}
int main()
{
	v[++nr]=2;
	
	for(int i=3;i<=1000000;i+=2)
		if(!c[i])
		{
			v[++nr]=i;
			for(int j=i+i;j<=1000000;j+=i)
				c[j]=1;
		}
	fscanf(f,"%d",&t);
	
	for(int o=1;o<=t;++o)
	{
		fscanf(f,"%lld",&n);
		int x=0;
		for(int i=1;i<=nr&&n>1;++i)
		{
			if(n%v[i]==0)
			{
				++x;
				w[x].p=v[i];
				while(n%v[i]==0)
				{
					w[x].e++;
					n/=v[i];
				}
			}
		}
		if(n>1)
		{
			w[++x].e=1;
			w[x].p=n;
		}
		int p=1;
		for(int i=1;i<=x;++i)
			p*=(w[i].e+1);
		fprintf(g,"%d ",p);
		int s=1;
		for(int i=1;i<=x;++i)
		{
			int y=(put(w[i].p%mod,w[i].e+1)-1+mod)%mod;
			y=(y*put((w[i].p-1)%mod,mod-2))%mod;
			s=(s*y)%mod;
		}
		fprintf(g,"%d\n",s);
		for(int i=1;i<=x;++i)
			w[i]=w[0];
	}
	
	
	
	fclose(g);
	fclose(f);
	return 0;
}