Cod sursa(job #522658)
#include <stdio.h>
#define LL long long
#define M 9973
LL i,j,t,id,nrpr;
LL N,pr2[250000],S,Div;
bool pr[500010];
void ciur()
{
pr2[0]=2; nrpr=0;
for(i=1;i<=500000;i++)
{
if(!pr[i])
{
for(j=2*i*i+2*i;j<=500000;j+=2*i+1)
pr[j]=true;
pr2[++nrpr]=2*i+1;
}
}
}
LL pow(LL c, LL p)
{
LL R=1;
while(p>1)
{
if(p&1) R*=c;
c*=c;
c%=M;
p>>=1;
}
return R;
}
void factori()
{
LL c,p,A=N;
S=Div=1;
for(i=0;pr2[i]*pr2[i]<=A && N>1;i++)
{
if(N%pr2[i]==0)
{
c=pr2[i]; p=0;
while(N%pr2[i]==0)
{
N/=pr2[i];
p++;
}
S*=(((LL)(pow(c,p+1)-1)/(c-1)) % M);
S%=M;
Div*=(p+1);
}
}
if(N>1)
{
Div*=2;
S*=((1LL*(N+1)) % M);
S%=M;
}
}
int main()
{
freopen("ssnd.in","r",stdin);
freopen("ssnd.out","w",stdout);
scanf("%lld",&t);
ciur();
for(id=1;id<=t;id++)
{
scanf("%lld",&N);
factori();
printf("%lld ",Div);
printf("%lld\n",S);
}
}