#include<fstream>

const long long Nmax = 1000006;
const int MOD = 9973;

using namespace std;

char ciur[Nmax];
long long nn=1000006 ;
long long n;

ifstream fin("ssnd.in");
ofstream fout("ssnd.out");

void Ciur ()
{
	long long i = 0 ,j = 0;
	for(i=4; i<=nn; i+=2)
	{
		ciur[i]='1';
		ciur[i+1]='0';
	}

	for(i=3; i<=nn; i+=2)
		if(ciur[i] == '0' ) 
		{
			j = i*i;
			for( ; j<=nn; j += (i+i))
				if(ciur[j] == '0')
					ciur[j]='1';
		}
}

long long t[1003];

void ReadData()
{
	fin>>n;
	for( int i=0;i<n;i++)
	{
		fin>>t[i];
		/*if( nn < t[i])
			nn = t[i];*/
	}
}
int nr=1;
int suma=1;
void Num ( int i, int j )
{
	int aux = t[i];
	int putere = 1;
	int nr_div = 0;
	while( aux % j == 0)
	{
		putere *= j;
		nr_div ++ ;
		aux = aux /j;
	}
	putere = putere % MOD;
	suma = suma * ((putere * j  - 1) / (j-1));
	suma = suma % MOD;
	nr = nr * (nr_div + 1);
}

void Sol()
{
	int i,j;
	for( i = 0; i<n; i++)
	{		
		nr = 1;
		suma = 1;
		if( ciur[t[i]] == 0) 
		{
			nr = 2;
			suma = t[i]+1;
		}
		else
		{
			if( t[i] % 2 == 0 )
				Num(i,2);
			for( j = 3; 2*j <= t[i]; j += 2)
				if( ciur[j] == 0)
					if( t[i] % j == 0 )
						Num(i,j);
		}
		fout<<nr<<" "<<suma<<"\n";
	}
}

int main()
{
	ReadData();
	Ciur();
	Sol();
	fout.close();
	fin.close();
	return 0;
}