#include<fstream>
#include<cmath>
#include<bitset>
using namespace std;

const int MAX = 1000001, MOD = 9973;
bitset<MAX> bs; // bs[i] = 0 if i is prime (and it is not even)

void ciur() {
	int i, j, root;
	root = (int) sqrt(MAX);
	for(i = 3; i <= root; i++) {
		for(j = i*i; j <= MAX; j += i << 1) {
			bs[j] = 1;
		}
	}
}

int main() {
	int t, x, i, sum, nr, j;
	double root;
	ifstream fin("ssnd.in");
	ofstream fout("ssnd.out");
	ciur();
	fin >> t;
	for(i = 0; i < t; i++) {
		fin >> x;
		root = sqrt(x);
		nr = 2; // 1 and x are included
		sum = (1 + x) % MOD;
		if(x % 2 == 0 && x > 4) {
			// the case x == 4 is treated with the perfect squares
			nr += 2;
			sum += (2 + x/2);
			sum %= MOD;
		}
		if(root * root == x) {
			// perfect square
			nr += 1;
			sum += (int) root;
			sum %= MOD;
			root--;
		}
		for(j = 3; j <= (int) root; j += 2) {
			if(bs[j] == 0 && x % j == 0) {
				nr += 2;
				sum += j + x/j;
				sum %= MOD;
			}
		}

		fout << nr << " " << sum << "\n";
	}
	return 0;
}