T=int(input())
l=[]
for i in range(T):
    cnt=0
    n=int(input())
    for j in range (n):
        if n%(j+1)==0:
            cnt+=1
    
    #print(cnt)   
    if(cnt%2==1):
        l.append('P')
    else:
        l.append('K')

for i in range (T):
    print(l[i])