const int Safe=;

 int gcd(int a,int b){return !b?a:gcd(b,a%b);}

 int mul(int a,int b,int p){

     int tmp=(a*b-(int)((double)a/p*b+1e-)*p);

     return tmp<?tmp+p:tmp;

 }

 int pow(int a,int b,int p){

     int ans=;a%=p;

     for(int i=b;i;i>>=,a=mul(a,a,p))

         if(i&)ans=mul(ans,a,p);

     return ans;

 }

 bool check(int a,int n,int r,int s){

     int ans=pow(a,r,n),p=ans;

     for(int i=;i<=s;i++){

         ans=mul(ans,ans,n);

         if(ans==&&p!=&&p!=n-) return true;

         p=ans;

     } if(ans!=)return true;return false;

 }

 bool MR(int n){

     if(n<=) return false;

     if(n==) return true;

     if(!(n&)) return false;

     int r=n-,s=;

     while(!(r&)) r>>=,s++;

     for(int i=;i<Safe;i++)

         if(check(rand()%(n-)+,n,r,s)) return false;

     return true;

 }

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #define ll long long

 #define inf 1000000000

 #define Safe 5

 using namespace std;

 ll gcd(ll a, ll b){

     return b ==  ? a : gcd(b, a % b);

 }

 ll n, x, mx;

 ll mul(ll a, ll b, ll p){

     ll tmp = (a * b - (ll)((long double)a / p * b + 1e-) * p);

     return tmp <  ? tmp + p : tmp;

 }

 ll pow(ll a, ll b, ll p){

     ll ans = ; a %= p;

     for(ll i = b; i; i >>= , a = mul(a, a, p))

         if(i & ) ans = mul(ans, a, p);

     return ans;

 }

 bool check(ll a, ll n, ll r, ll s){

     ll ans = pow(a, r, n), p = ans;

     for(int i = ; i <= s; i ++){

         ans = mul(ans, ans, n);

         if(ans ==  && p !=  && p != n - ) return true;

         p = ans;

     }

     if(ans != )return true;

     return false;

 }

 bool MR(ll n){

     if(n <= ) return false;

     if(n == ) return true;

     if(n %  == ) return false;

     ll r = n - , s = ;

     while(r %  == ) r /= , s ++;

     for(int i = ; i < Safe; i ++)

         if(check(rand() % (n - ) + , n, r, s)) return false;

     return true;

 }

 ll rho(ll n, ll c){

     ll k = , x = rand() % n, y = x, p = ;

     for(ll i = ; p == ; i ++){

         x = (mul(x, x, n) + c) % n;

         p = y > x ? y - x : x - y;

         p=gcd(n, p);

         if(i == k) y = x, k += k;

     }

     return p;

 }

 void solve(ll n){

     if(n == ) return;

     if(MR(n)) { mx = max(n, mx); return; }

     ll t = n;

     while(t == n) t = rho(n, rand() % (n - ) + );

     solve(t); solve(n / t);

 }

 void read(ll &x){

     x = ; ll sig = ; char ch = getchar();

     while(!isdigit(ch)) { if(ch == '-') sig = -; ch = getchar(); }

     while(isdigit(ch)) x =  * x + ch - '', ch = getchar();

     x *= sig; return ;

 }

 ll cnt = ;

 void init(){

     read(n);

     cnt = ;

     return ;

 }

 void work(){

     while(n --){

         read(x);

         if(MR(x)) cnt ++;

         mx = ; solve(x);

         if(mx == x) puts("Prime");

         else printf("%lld\n", mx);

     }

     return ;

 }

 void print(){

     printf("%lld\n", cnt);

     return ;

 }

 int main(){

     init();

     work();

     print();

     return ;

 }