#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;

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

#define MAX 1000010
long long a[1010][3],t;

long long n;

bool V[MAX];

void div(long long &n,int d,long long &a,long long &b)
{
    long long pr=1,nd=0;
	while(n!=1 && n%d==0)
	{
		nd++;
		pr=pr*d;
		n=n/d;
				
	}
	a=a * (nd+1);
    b=(b* (pr*d-1)/(d-1))%9973;
}

int main()
{
	in>>t;
	int i,j;
	for(i=1;i<=t;i++)
	{
		a[i][1]=a[i][2]=1;
	    in>>a[i][0];
		if(a[i][0]==1)
			a[i][0]=-1;
	}
	for(i=2;i<=MAX;i++)
	{
		if(V[i]==0)
		{
			for(j=1;j<=t;j++)
		 	 if(a[j][0]>1)
			   div(a[j][0],i,a[j][1],a[j][2]);
		    for(j=2;j<=MAX/i;j++)
			   V[i*j]=1;
		}
	}
	for(i=1;i<=t;i++)
	{
		if(a[i][0]>MAX)
			a[i][2]=(a[i][2] +a[i][0])%9973;

		out<<a[i][1]<<' '<<a[i][2]<<'\n';
	}

	in.close();
	out.close();
	return 0;
}