Cod sursa(job #532033)
#include <stdio.h>
#include <vector>
using namespace std;
const int MOD = 9973;
vector<int> primes;
void calcNdivSdiv(long long n, int* nndiv, long long* ssdiv) {
int ndiv = 1;
long long sdiv = 1;
int div = 0;
int nr;
long long divPowNr;
while ((long long) primes[div] * primes[div] <= n) {
if (n%primes[div] == 0) {
nr = 1;
divPowNr = primes[div];
n/=primes[div];
while (n%primes[div] == 0) {
++nr;
divPowNr *= primes[div];
n /= primes[div];
}
if (nr) {
ndiv *= (nr + 1);
sdiv *= (divPowNr*primes[div] - 1) / (primes[div]-1);
}
}
div++;
}
if (n != 1) {
ndiv *= 2;
sdiv *= (n+1);
}
*nndiv = ndiv;
*ssdiv = sdiv;
}
void compute_primes(int n) {
primes.clear();
vector<char> prim(n, true);
for(int i=2; i<=n; i++)
if( prim[i]==1 ) {
for(int j=2*i; j<=n; j+=i) prim[j] = 0;
primes.push_back(i);
}
}
int main() {
freopen("ssnd.in", "r", stdin);
freopen("ssnd.out", "w", stdout);
int nrt;
scanf("%d", &nrt);
compute_primes(1001000);
while (nrt--) {
long long n;
scanf("%lld", &n);
long long sdiv;
int ndiv;
calcNdivSdiv(n, &ndiv, &sdiv);
printf("%d ", ndiv % MOD);
printf("%d\n", sdiv % MOD);
}
return 0;
}