#include<fstream>
using namespace std;
ofstream g("ssnd.out");
const int mod=9973, maxn=1000009;
int n, p[maxn], e[maxn];
void dec(int x){
	int d;
	for(d=2, n=-1;d*d<=x;d++)
		if(x%d==0){
			n++;p[n]=d;e[n]=0;
			while(x%d==0){
				e[n]++;
				x/=d;
			}
		}
	if(x!=1){
		n++;p[n]=x;e[n]=1;
	}
}
void ndiv(){
	int i, p=1;
	for(i=0;i<=n;i++){
		p*=(++e[i]);
		p=p%mod;
	}
	g<<p<<' ';
}
int minv(int x){
	int i, m=mod-2, p=1;
	for(i=0;i<m;i++){
		p=p*x;
		p=p%mod;
	}
	return p;
}
int Term(int poz){
	int i, pow=1, inv;
	for(i=0;i<e[poz];i++){
		pow=pow*p[poz];
		pow=pow%mod;
	}
	pow--;
	if(pow>=mod)	pow-=mod;
	if(pow<0)	pow+=mod;
	inv=minv((p[poz]-1)%mod);
	pow=pow*inv;
	pow=pow%mod;
	return pow;
}
void sdiv(){
	int i, s=1;
	for(i=0;i<=n;i++){
		s*=Term(i);
		s=s%mod;
	}
	g<<s<<'\n';
}
int main(){
	int i, t, x;
	ifstream f("ssnd.in");
	f>>t;
	for(i=0;i<t;i++){
		f>>x;
		dec(x);
		ndiv();
		sdiv();
	}
	f.close();
	g.close();
	return 0;
}