#include <bits/stdc++.h>
#include <boost/multiprecision/miller_rabin.hpp>
using namespace std;

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  long N, X;
  cin >> N;
  while (cin >> X) cout << X << " " << boost::multiprecision::miller_rabin_test(X, 10) << "\n";
}