def divisors(n):
    ldivisors, udivisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            ldivisors.append(i)
            if i != n // i:
                udivisors.append(n//i)
        i += 1

    return ldivisors + udivisors[::-1]

t = int(input())

for i in range(t):
    n = int(input())
    a = divisors(n)
    if len(a) % 2 == 0:
        print("K")
    else:
        print("P")