#include <fstream>
using namespace std;
ifstream cin("ssnd.in");
ofstream cout("ssnd.out");
int mod = 9973;
long long nrDiv(long long &a)
{
  long long s = a + 1, nr = 2;
  for (long long i = 2; i * i <= a; i++)
    if (a % i == 0)
    {
      s += i, nr++, s %= mod;
      if (i * i < a)
        s += a / i, nr++, s %= mod;
    }
  a = s;
  return nr;
}
int main()
{
  long long n, x;
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> x;
    cout << nrDiv(x) << ' ' << x << endl;
  }
  cout.close();
  return 0;
}