#include<iostream>
#include<fstream>

using namespace std;
void fun(long n,long &nr,long &s)
{long i;
s=n+1;
nr=2;
for(i=2;i<=n/2;i++)
	if(n%i==0)
	{
		s=s+i;
		nr++;}
}
	

int main()
{
	ifstream f("ssnd.in");
	ofstream g("ssnd.out");
	long n,x,s,nr,v[100],i,max;
	f>>n;
	f>>max;
	for(i=2;i=n;i++)
	{
		f>>z[i];
		if(z[i]>max)
			max=z[i];
	}
	
	for(i=1;i<=max;i++)
		v[i]=0;
	
	
	for(i=2;i<=max;i++)
	{
		if(v[z[i]]==0)
		{
			c=2*i;
			while(c<=max)
			{
				v[c]=1;
				c=c+i;
			}
			i++;
		}
	}
		

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