def divn(n):
    res = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.add(i)
            if not n//i in res:
                res.add(n//i)
    return res

for _ in [0]*int(input()):
    n = int(input())
    if len(divn(n)) % 2 == 0:
        print("K")
    else:
        print("P")