for _ in range(int(input())):
    N=int(input())
    s = set()
    num = 1
    for i in range(1,N+1):
        if i*i > N:
            break
        elif i*i == N:
            num += 1
        else:
            if N%i == 0:
                num += 2
    
    if num%2 == 0:
        print("P")
    else:
        print("K")