import sys
# sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd

def eratosthenes(n):
    is_prime = ([False, True] * (n//2+1))[0: n+1]
    is_prime[1] = False
    is_prime[2] = True
    for i in range(3, n+1, 2):
        if not(is_prime[i]):
            continue
        if i*i > n:
            break
        for k in range(i*i, n+1, i):
            is_prime[k] = False
    return is_prime

def sol():
    n = int(input())
    cnt=0
    if n == 1:
        cnt=0
    else:
        cnt = eratosthenes(n).count(True)
    
    if cnt % 2:
        print('K')
    else:
        print('P')

T = int(input())
for i in range(T):
    sol()