for _ in range(T := int(input())):
  N = int(input())

  div_cnt = 0
  for i in range(1, int(N**0.5)+1):
    if N%i == 0: div_cnt += 2
  if i**2 == N: div_cnt -= 1

  print('K' if div_cnt%2 == 0 else 'P')