from collections import deque
MAX = 3*10**6+10

def Sieve_of_Eratosthenes(N):
    flag=[False]*2+[True]*(N-1)
    for i in range(2,round((N+1)**0.5)+1):
        if flag[i]:
            for j in range(i**2,N+1,i):
                flag[j]=False
    return flag

isPrime = Sieve_of_Eratosthenes(MAX)

ans = [0 for i in range(MAX)]
cantuse = 0
dq = deque()
for i in range(2,MAX):
    if dq:
        if dq[0]*2 <= i:
            cantuse -= 1
            dq.popleft()
    if isPrime[i]:
        cantuse += 1
        dq.append(i)
    else:
        ans[i] = i-2-cantuse


for _ in range(int(input())):
    N=int(input())
    
    if ans[N]%2 == 0:
        print("P")
    else:
        print("K")