def gen_divisors(n):
    a = []
    for i in range(1,n+1):
        if i*i>n: break
        if n%i==0:
            a.append(i)
            if i*i<n: a.append(int(n/i))
    #a.sort()
    return a
T=int(input())
for _ in range(T):
    N=int(input())
    A=gen_divisors(N)
    if len(A)%2==0:print("K")
    else:print("P")