import sympy
T = int(input())
for t in T:
    N = int(input())
    turn_needed = len(sympy.divisors(N))
    if turn_needed%2 == 1:
        print("P")
    else:
        print("K")