#include <bits/stdc++.h>

#define all(v) begin(v), end(v)

using namespace std;

const int MOD = 1e9 + 7;

long long modpow(long long a, long long n, long long m = MOD) {
  if (n <= 0) return 1LL;
  if (n % 2LL) return a * modpow(a, n-1) % MOD;
  long long t = modpow(a, n/2);
  return t % MOD * t % MOD;
}


bool isPrime(long long n) {
  if (n == 2) return true;
  if (n == 1 || n % 2 == 0) return false;

  long long m = n - 1;
  long long s = 0;

  while (m % (1LL << s) == 0) ++s;

  long long d = m / (1LL << s);

  vector<long long> testNumbers {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

  for (auto a : testNumbers) {
    if (a == n) continue;
    
    long long x = modpow(a, d, n);
    int r = 0;

    if (x == 1) continue;

    while (x != m) {
      x = modpow(x, 2, n);
      ++r;

      if (x == 1 || r == s) return false;
    }
  }

  return true;
}


signed main() {
  int n;
  cin >> n;

  for (int i = 0; i < n; ++i) {
    long long x;
    cin >> x;

    cout << x << " " << isPrime(x) << endl;
  }

  return 0;
}