from math import gcd

def soln(N):
    vis = [False] * (N + 1)
    vis[1] = True  
    
    def find_coprime(x):
        for i in range(2, N + 1):
            if vis[i] or gcd(x, i) == 1:
                continue
            return i
        return -1
    
    x = 2
    while True:
        y = find_coprime(x)
        if y == -1:
            return "K"
        vis[y] = True
        x = y
        
        y = find_coprime(x)
        if y == -1:
            return "P"
        vis[y] = True
        x = y

T = int(input())
for _ in range(T):
    N = int(input())
    print(soln(N))