#include<fstream>
using namespace std;
int main()
{unsigned long long n[1000], j, s, c;
int t, i, OK, r;
ifstream f("ssnd.in");
ofstream h("ssnd.out");
f>>t;
for (i=1; i<=t; i++)
	f>>n[i];
for (i=1; i<=t; i++)
{c=1;
s=n[i];
for (j=1; j<=n[i]/2; j++)
	{OK=1;		
	if (n[i]%j==0)
		OK=0;
	if (OK==0)
	{c++;
	s=s+j;}
	}	
h<<c<<" ";
r=s%9973;
h<<r<<endl;
	}
	
	
	f.close();
	h.close();
	return 0;
}