#include<bits/stdc++.h>
using namespace std;

vector<bool> Eratosthenes(int N) {
    vector<bool> isprime(N+1, true);
    isprime[0] = isprime[1] = false;
    for (int p = 2; p <= N; ++p) {
        if (!isprime[p]) continue;
        for (int q = p * 2; q <= N; q += p) {
            isprime[q] = false;
        }
    }
    return isprime;
}

int main(){
	int N_max = 3000000;
	vector<bool> is_prime = Eratosthenes(N_max);
	vector<int> prime_count(N_max+1);//prime_count[i] : i以下の素数の個数
	int count=0;
	for(int i=0;i<prime_count.size();i++){
		if(is_prime[i]){
			count++;
		}
		prime_count[i] = count;
	}
	int T;
	cin >> T;
	for(int i=0;i<T;i++){
		int N,S_size;
		cin >> N;
		if(is_prime[N]){
			cout << "P" << endl;
		} else {
			S_size = N-(1+prime_count[N]-prime_count[N/2]);
			if(S_size%2 == 1){
				cout << "P" << endl;
			} else {
				cout << "K" << endl;
			}
		}
	}
}