def norm(m, n)
  m**2 + n**2
end

def isGaussPrime(real, imaginary)
  real, imaginary = real.abs, imaginary.abs
  if real == 0
    return imaginary&3 == 3 && isPrime(imaginary)
  end
  if imaginary == 0
    return real&3 == 3 && isPrime(real)
  end
  isPrime(norm(real, imaginary))
end

def isPrime(n)
  return n == 2 if n&1 == 0
  for i in 3...n do
    return false if n % i == 0
  end
  n != 1
end

gets.to_i.times do
  m, n = gets.split.map(&:to_i)
  puts isGaussPrime(m, n) ? "P" : "C"
end