from math import gcd
Q=int(input())
for _ in range(Q):
  N=int(input())
  if N==2:
    print('P')
    continue
  for x in range(2,N+1):
    if N%x!=0:
      z=x
      break
  if gcd(N,x)==1:
    print('K')
  else:
    print('P')