n = gets.to_i
n.times do
    p, q = gets.split.map(&:to_i)
    count = 0
    -145.upto(145) do |i|
        -145.upto(145) do |j|
            next if i == 0 && j == 0
            count += 1 if (i * p + j * q) % (i * i + j * j) == 0 && (i * q - j * p) % (i * i + j * j) == 0
        end
    end
    puts count == 8 ? "P" : "C"
end