#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <cassert>
#include <bitset>
#include <map>
#include <algorithm>
#include <iterator>
#include <string>
#include <utility>
#include <numeric>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using P=pair<ll,ll>;
#define reps(i,a,n) for(int i=a;i<n;i++)
#define rep(i,n) reps(i,0,n)
#define all(x) x.begin(),x.end()
vector<ll>a{2,325,9375,28178,450775,9780504,1795265022};
bool solve(ll n){
  if(n==1)return 0;
    ll d=n-1;
    int s=0;
    while(d%2==0){d/=2;s++;}
    rep(i,7){
        if(a[i]%n==0)continue;
        ll ad=pow_mod(a[i],d,n);
        if(ad==1||ad==n-1)continue;
        bool ok=true;
        rep(j,s+1){
            ad*=ad;
            ad%=n;
            if(ad==n-1)ok=false;
        }
        if(ok){
            return false;
        }
    }
    return true;
}
int main(){
  int n;
  cin>>n;
  rep(i,n){
    ll x;
    cin>>x;
    cout<<x<<' '<<solve(x)<<endl;
  }
}