#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <random>
#include <cassert>

using ll = long long;

template<class T>
T power(T x, T y, T p) {
	T res = 1;
	x = x % p;
	while (y) {
		if (y % 2 != 0)res = (res * x) % p;
		y /= 2;
		x = (x * x) % p;
	}
	return res;
}

ll uniformInteger(const ll& lower, const ll& upper) {
	assert(lower <= upper);
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	std::uniform_int_distribution<> rng(0, upper);
	ll rn = rng(mt);
	return rn + lower;
}

const int bound_mrpt = 2e1; // Pr = 1 / 4^bound_mrpt
bool MillerRabbinPrimalityTest(const ll& n, const int bound = bound_mrpt) {
	if (n<0) return false;
  if (n <= 1) return false;
	if (n == 2) return true;
	if (n % 2 == 0)return false;

	ll d = n - 1;
	int s = 0;
	for (;;) {
		if (d%2 != 0)break;
		d = d/2;
		++s;
	}
	for (int k = 0; k < bound; ++k) {
		ll a(uniformInteger(1, n - 1));
		ll ad(power(a, d, n));
		//std::cout << a << "\t" << ad << "\n";
		if (ad == 1) continue;
		for (int r = 1; r < s && ad != n - 1; ++r) {
			ad = (ad * ad) % n;
		}
		if (ad == n - 1)continue;
		else return false;
	}
	return true;
}


int main() {
	int n;
	std::cin>>n;
	while(n--){
	    ll p;
	    std::cin>>p;
	    std::cout<<p<<" "<<(MillerRabbinPrimalityTest(p)?1:0)<<std::endl;
	}
}