def gcd(a, b):
  while a != 0:
    b %= a
    if b == 0: return a
    a %= b
  return b

T = int(input())
for _ in range(T):
  N = int(input())
  if N == 2:
    print('P')
    continue
  if N % 2:
    print('K')
    continue
  for p in range(2,N+1):
    if N % p == 0:
      continue
    break
  if gcd(N,p) > 1:
    print('P')
  else:
    print('K')