T = int(input())

def f(n):
    ret = []
    for i in range(1,int(n**(1/2))+10):
        if(i*i > n):break
        if(n%i == 0):
            ret.append(i)
            ret.append(n//i)
    return len(set(ret))

for _ in range(T):
    N = int(input())
    print("P" if f(N)%2 == 1 else "K")