#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define all(x) (x).begin(),(x).end() #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=3000005,INF=15<<26; int dp[1<<23]; int solve(int X){ if(dp[X]!=-1) return dp[X]; int ma=-1; for(int i=22;i>=0;i--){ if(X&(1<<i)){ ma=i; break; } } for(int j=2;j<ma;j++){ if(X&(1<<j)) continue; bool ok=false; for(int k=2;k<=ma;k++){ if(X&(1<<k)){ if(gcd(j,k)>1) ok=true; } } if(ok){ if(!solve(X|(1<<j))) return dp[X]=1; } } return dp[X]=0; } vector<int> prime;//i番目の素数 int is_prime[MAX+1]; void sieve(int n){ for(int i=0;i<=n;i++){ is_prime[i]=true; } is_prime[0]=is_prime[1]=false; for(int i=2;i<=n;i++){ if(is_prime[i]){ prime.push_back(i); for(int j=2*i;j<=n;j+=i){ is_prime[j] = false; } } } for(int i=1;i<=n;i++) is_prime[i]+=is_prime[i-1]; } int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); memset(dp,-1,sizeof(dp)); for(int N=2;N<=22;N++){ //cout<<N<<" "<<solve(1<<N)<<endl; } sieve(MAX-2); int Q;cin>>Q; while(Q--){ int N;cin>>N; if(is_prime[N]-is_prime[N-1]){ cout<<"P\n"; continue; } int sum=N-2; sum-=(is_prime[N-1]-is_prime[N/2]); if(sum%2==0) cout<<"P\n"; else cout<<"K\n"; } }