import sys
input = sys.stdin.readline

from math import gcd

T=int(input())
for tests in range(T):
    N=int(input())

    OK=set()

    for i in range(2,N):
        if N%i!=0:
            OK.add(i)
        if gcd(i,N)==1:
            start=i
            break

    #print(start,OK)

    if N==2 or min(OK)!=start:
        print("P")
    else:
        print("K")