#include<iostream>
#include<math.h>
#include<fstream>
using namespace std;
ifstream f("ssnd.in");
ofstream g("ssnd.out");
long long n;
long v[1000];
void ciur(long max)
{
	long i,c;
	for(i=1;i<=max;i++)
	{
		if(v[i]==0)
		{
			for(c=2*i;c<=max;c=c+i)
				v[c]=1;
		}
	}
}
void divid(long x,long &nr,long &s)
{
	long i=2, a[1000], b[1000],c=0,p;
	nr=0;
	while(x!=1)
	{
		if(x%i==0)
		{
			c++;
			nr=0;
			a[c]=i;
		     while(x%i==0)
				 {
					 nr++;
					 x=x/i;
			     } 
			 b[c]=nr;
		}
		i++;
	}
	nr=1;
	s=1;
	for(i=1;i<=c;i++)
		{
			nr=nr*(a[i]+1);
			p=pow(a[i],b[i]);
			s=s*((p-1)/(a[i]-1));
	}
	
		
}
int main()
{
	f>>n;
	long i,max,arr[1000],nr,s;
	f>>max;

	for(i=2;i<=n;i++)
	{
		f>>arr[i];
		if(arr[i]>max)
			max=arr[i];
	}
	ciur(max);
	for(i=1;i<=n;i++)
	{
		if(v[arr[i]]==0)
			g<<2<<" "<<(arr[i]+1)%9973<<"\n";
		else
		{
			divid(arr[i],nr,s);
			g<<nr<<" "<<s%9973<<"\n";
		}
	}
	f.close();
	g.close();
	return 0;
}