#include<fstream.h>
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
const int c=9973;
int t,a[1000];
int exponentiere(long long a, long long p)
{
	unsigned int i;
	long long sol=1;
	for(i=0;(1<<i)<=p;i++)	// luam toti biti lui p la rand
	{
		if(((1<<i)&p)>0)// daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
			sol=(sol*a);
		a=(a*a)%100000;// inmultim a cu a ca sa obtinem n^(2^i+1);
	}
	//fout<<sol<<'\n';
	return sol;
}
int descompunere(int x)
{
	int d=2,fm,nr=1,s=1;
	while(x>1)
	{
		fm=0;
		while(x%d==0)
		{
			fm=fm+1;
			x=x/d;
		}
			nr=nr*(fm+1);
			s=s*(exponentiere(d,fm+1)-1)/(d-1);
			d=d+1;
	}
	fout<<nr<<' '<<s%c<<'\n';
	return 0;
}

/*void divizori(int x)
{
	
	int i,nr=0,s=0;
	for(i=1;i<=x;i++)
		if(x%i==0)
		{
			nr++;
			s=s+i;
		}
	fout<<nr<<' '<<s<<'\n';
}*/
int main()
{
	int i,nr,d,s;
	fin>>t;
	
	for(i=1;i<=t;i++)
	{
		fin>>a[i];
		descompunere(a[i]);
	}
	
	return 0;
}