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

using ll = long long;
using llu = long long unsigned;

// メイン関数
int main() {
    int t;
    cin >> t;

    for (int i=0; i<t; ++i) {
        int n;
        cin >> n;
        set<int> yakusu;
        for (int i=1; i*i<=n; ++i) {
            if (n%i == 0) {
                yakusu.insert(i);
                yakusu.insert(n/i);
            }
        }
        if (yakusu.size() % 2) {
            cout << "P" << endl;
        } else {
            cout << "K" << endl;
        }
    }
    return 0;
}