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

T = int(input())
for _ in range(T):
    N = int(input())
    if N == 2:
        print("P")
    elif N == 3:
        print("K")
    else:
        for i in range(3, N + 1):
            if N % i == 0:
                continue
            print("K") if gcd(i, N) == 1 else print("P")
            break