import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt();
            System.out.println(find(n)%2==0?"K":"P");
        }
    }
    static int find(int a){
        int ans=1;
        for(int i=2;i*i<=a;i++){
            int count=0;
            while(a%i==0){
                count++;
                a/=i;
            }
            ans*=count+1;
        }
        if(a!=1){
            ans*=2;
        }
        return ans;
    }
}