#include <stdio.h>

long long gcd (long long a, long long b) {
  if (b <= 0LL) {
    return a;
  }
  return gcd(b, a%b);
}

int main () {
  int t = 0;
  long long n = 0LL;
  
  int res = 0;
  
  res = scanf("%d", &t);
  while (t > 0) {
    long long p = 2LL;
    long long q = 2LL;
    res = scanf("%lld", &n);
    while (n%p == 0LL) {
      p += 1LL;
    }
    while (p%q != 0LL) {
      q += 1LL;
    }
    if (p > n || n%q == 0LL) {
      printf("P\n");
    } else {
      printf("K\n");
    }
    t--;
  }
  
  return 0;
}