import sys
input = sys.stdin.readline


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

st = set([i ** 2 for i in range(1, 10 ** 6 + 1)])
for n in query:
    if(n in st):
        print('P')
    else:
        print('K')