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

#include <boost/multiprecision/miller_rabin.hpp>
using namespace boost::multiprecision;

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