#include <atcoder/internal_math>
#include <iostream>
using namespace std;
using namespace atcoder::internal;

int main(){
	int n;
	cin>>n;
	while(n--){
		long long x;
		cin>>x;
		cout<<x<<" "<<is_prime_constexpr(x)<<endl;
	}
}