import math for _ in range(int(input())): N=int(input()) Ncopy = N LoseNum = 2 for i in range(2,min(N,1000)): isLosenum = True if N%i == 0: isLosenum = False if isLosenum: LoseNum = i break if math.gcd(Ncopy,LoseNum) != 1: print("P") else: print("K")