import math
def sympy(N):
    """Nの正の約数の数を返す"""
    ans = 0
    if N == 1:
        return 1
    now = 1
    while now <= math.sqrt(N):
        if N%now == 0:
            if now == math.sqrt(N):
                ans += 1
            else:
                ans += 2
        
        now += 1
    return ans
#for k in range(1, 10):
#    print(k, sympy(k))
T = int(input())
for t in range(T):
    N = int(input())
    turn_needed = sympy(N)
    if turn_needed%2 == 1:
        print("P")
    else:
        print("K")