for _ in range(int(input())):
    N = int(input())
    num_divisors = 0
    for d in range(1, N + 1):
        if d * d > N:
            break
        if d * d == N:
            num_divisors += 1
        elif N % d == 0:
            num_divisors += 2
    if num_divisors % 2 == 0:
        print('K')
    else:
        print('P')