Q=int(input())
for _ in range(Q):
  N=int(input())
  ans=1
  for x in range(2,N+1):
    if N%x==0:
      count=0
      while N%x==0:
        N/=x
        count+=1
      ans*=count+1
  if ans%2==1:
    print('P')
  else:
    print('K')