import std.stdio;
import std.string;
import std.conv;

void main(){
  auto T = readln.chomp.to!int;
  for(auto t = 0; t < T; t++){
    auto N = readln.chomp.to!int;
    auto c = 0;
    for(auto n = 1; n ^^ 2 <= N; n++){
      if(N % n) continue;
      c += 2;
      if(n ^^ 2 == N) c--;
    }
    writefln("%c", c % 2 ? 'P' : 'K');
  }
}