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

vector<ll> P = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};

bool solve() {
  ll N;
  cin >> N;

  if(N == 2) { return false; }

  ll p;
  for(auto &i : P) {
    if(N % i) {
      p = i;
      break;
    }
  }

  for(ll i = 1; i < p; i++) {
    if(N % i) { return false; }
  }

  return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll t;
  cin >> t;
  while(t--) { cout << (solve() ? "K" : "P") << "\n"; }
}