#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
int main () {
	int T;
	cin >> T;
	while (T--) {
		ll N;
		cin >> N;
		int fl = 2;
		while (N % fl == 0) fl ++;
		cout << (gcd(N, fl) == 1 ? "K" : "P") << endl;
	}
}