#include <bits/stdc++.h>
using namespace std;

#include <boost/multiprecision/miller_rabin.hpp>
#include <boost/random/mersenne_twister.hpp>
using namespace boost::multiprecision;
boost::random::mt19937 gen;

int main() {
  long N, X;
  cin >> N;
  while (cin >> X) cout << X << " " << miller_rabin_test(X, 10, gen) << "\n";
}