from math import gcd
for _ in range(int(input())):
    n = int(input())
    for i in range(2,n+1):
        if n%i: break
    print("K" if i<n and gcd(i,n)==1 else "P")