#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("ssnd.in");
ofstream fout("ssnd.out");

struct stupit{
	int k, l;
};

bool frecu[1000041];
vector<int> primes;
void primeit(){
	for(int i = 2; i <= 1000000; i++){
		if(!frecu[i]){
			primes.push_back(i);
			for(int j = i+i; j <= 1000000; j += i){
				frecu[j] = true;
			}
		}
	}
}

const int modit = 9973;
stupit verseit(int a, int b){
	if(b == 0){
		return {1, 0};
	}
	stupit pr = verseit(b, a%b);
	return {pr.l, pr.k-pr.l*(a/b)};
}

int inverseit(int a){
	return (verseit(a, modit).k + modit) % modit;
}

int n;
void solveit(){
	int a;
	fin >> a;
	
	int cer = 1, sol = 1;
	for(int i = 0; i < primes.size() && a != 1; i++){
		int p = primes[i], q = p, c = 1;
		while(a % p == 0){
			a /= p;
			q *= p;
			c++;
		}
		
		//ah, scheisse modular
		sol *= (q-1);
		sol *= inverseit(p-1);
		sol %= modit;
		
		cer *= c;
	}
	
	fout << cer << " " << sol << "\n";
}

int main(){
	primeit();
	fin >> n;
	for(int i = 0; i < n; i++){
		solveit();
	}
}