def solve():
    T = int(input().strip())
    for _ in range(T):
        N = int(input().strip())
        divisors = 0
        i = 1
        while i * i <= N:
            if N % i == 0:
                if N / i == i:
                    divisors += 1
                else:
                    divisors += 2
            i += 1
        if divisors % 2 == 0:
            print("K")
        else:
            print("P")

solve()