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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    const int m = 1000;
    vector<int> tb(m + 1, 1);
    for(int i = 2; i <= m; i++){
        for(int j = i; j <= m; j += i){
            tb[j]++;
        }
    }
    int T;
    cin >> T;
    while(T--){
        int v;
        cin >> v;
        cout << (tb[v] & 1 ? 'P' : 'K') << '\n';
    }
}