T = int(input()) C = 3 * 10 ** 6 + 5 prime = [] s = set() dat = [0] * C for i in range(2,C): if dat[i] == 0: prime.append(i) s.add(i) for j in range(i,C,i): dat[j] = 1 for _ in range(T): N =int(input()) if N in s: print("P") continue M = N // 2 start = 0 end = len(prime) while end - start > 1: mid = end + start >> 1 if prime[mid] <= M: start = mid else: end = mid i = end if prime[-1] <= N: j = len(prime) - 1 else: start = 0 end = len(prime) - 1 while end - start > 1: mid = end + start >> 1 if prime[mid] >= N:end = mid else:start = mid j = start K = N - 2 - (j - i + 1) print("K" if K % 2 == 1 else "P")