require "prime"
input = $<.read.split.map(&:to_i)
T = input.shift
T.times do
	n = input.shift
	d = n.prime_division.inject(1) { |d, (_, e)| d * (e + 1) } - 1
	if d.odd?
		puts "K"
	else
		puts "P"
	end
end