Cod sursa(job #688612)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
void erath(vector<long long> &prime)
{
long long i, j;
bitset<1000000> prim;
for(i=3;i<1000000;i+=2)
if(!prim[i])
{
prime.push_back(i);
for(j=i*i;j<1000000;j+=2*i)
prim[j] = 1;
}
}
int main()
{
short int t, j;
long long n[1005], i;
freopen("ssnd.in", "r", stdin);
cin>>t;
for(j=0;j<t;++j)
cin>>n[j];
freopen("ssnd.out", "w", stdout);
fclose(stdin);
vector<long long> prime(1, 2);
erath(prime);
vector<long long>::iterator it, end(prime.end());
int exp, nrdiv, sumadiv, z;
for(j=0;j<t;++j)
{
nrdiv = 1;
sumadiv = 1;
for(it=prime.begin(),i=0;i<=n[j];++it,++i)
{
exp = 0;
z = *it;
while(n[j] % *it == 0)
{
n[j] /= *it;
++exp;
z *= *it;
}
nrdiv *= (exp + 1);
sumadiv *= ((z-1) / (*it - 1))%9973;
}
cout<<nrdiv<<" "<<sumadiv%9973<<"\n";
}
fclose(stdout);
return 0;
}