#include<stdio.h>
#include<math.h>
#define mod 9973
using namespace std;
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(register int i=3;i<=1000000;i+=2)
		if(!c[i])
		{
			v[++nr]=i;
			for(register int j=i+i;j<=1000000;j+=i)
				c[j]=1;
		}
	fscanf(f,"%d",&t);
	
	for(register int o=1;o<=t;++o)
	{
		fscanf(f,"%lld",&n);
		int x=0;
		int nn=sqrt(n);
		int p=1;
		for(register int i=1;v[i]<=nn&&n>1;++i)
		{
			if(n%v[i]==0)
			{
				++x;
				w[x].e=0;
				w[x].p=v[i];
				while(n%v[i]==0)
				{
					w[x].e++;
					n/=v[i];
				}
				p*=(w[x].e+1);
			}
		}
		if(n>1)
		{
			w[++x].e=1;
			p*=2;
			w[x].p=n;
		}
	
		fprintf(g,"%d ",p);
		int s=1;
		for(register int i=1;i<=x;++i)
		{
		
			s=(s*(put(w[i].p%mod,w[i].e+1)-1+mod)%mod*put((w[i].p-1)%mod,mod-2))%mod;
		}
		fprintf(g,"%d\n",s);
		
	}
	
	
	
	fclose(g);
	fclose(f);
	return 0;
}