from collections import defaultdict, deque, Counter
from functools import cache
# import copy
from itertools import combinations, permutations, product, accumulate, groupby, chain
from heapq import heapify, heappop, heappush
import math
import bisect
from pprint import pprint
from random import randint, shuffle
import sys
# sys.setrecursionlimit(200000)
input = lambda: sys.stdin.readline().rstrip('\n')
inf = float('inf')
mod1 = 10**9+7
mod2 = 998244353
def ceil_div(x, y): return -(-x//y)

#################################################    

def factor(x):
    retm, retM = [], []
    i = 1
    while i*i <= x:
        if x%i == 0:
            retm.append(i)
            if x//i != i:
                retM.append(x//i)
        i += 1
    return retm+retM[::-1]

T = int(input())
for _ in range(T):
    N = int(input())
    print("P" if len(factor(N))%2 == 1 else "K")