#include<fstream.h>
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
const int c=9973;
int t,n;
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);
	}
	return sol;
}
void 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;
		}
		if(fm!=0)
		{
			nr=nr*(fm+1);
			s=s*(exponentiere(d,fm+1)-1)/(d-1);
		}
			d=d+1;
		
	}
	fout<<nr<<' '<<s%c<<'\n';
	
}
int main()
{
	int i,n;
	fin>>t;
	for(i=1;i<=t;i++)
	{
		fin>>n;
		descompunere(n);
	}
	return 0;
}