primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]

for _ in range(int(input())):
    N = int(input())
    if N == 2:
        print('P')
        continue
    for p in primes:
        if N % p == 0:
            continue
        if all(N % d == 0 for d in range(2, p)):
            print('K')
        else:
            print('P')
        break