N = 3000300
isprime = [True] * N
isprime[0] = isprime[1] = False
for i in range(2, N):
    if isprime[i]:
        for j in range(i * i, N, i):
            isprime[j] = False

pc = [0]
for i in range(1, N):
    pc.append(pc[-1] + isprime[i])


def solve():
    n = int(input())
    if isprime[n]:
        return True

    c = pc[n] - pc[n // 2]
    return (n - c) % 2 == 0


for _ in range(int(input())):
    if solve():
        print("P")
    else:
        print("K")