# frozen_string_literal: true
require 'prime'
t = gets.to_i
t.times do
  n = gets.to_i
  if n == 1
    puts 'P'
    next
  end
  ps = n.prime_division
  if ps.map { |e| e[1] + 1 }.reduce(:*).even?
    puts 'K'
  else
    puts 'P'
  end
end