import sys
from math import gcd
input = sys.stdin.readline

query = [int(input()) for _ in [0] * int(input())]

def solve(n):
    for i in range(2, n):
        if(n % i == 0):
            continue
        if(gcd(n, i) != 1):
            break
        return 'K'
    return 'P'

for n in query:
    print(solve(n))