### main

nd = gets.to_i

nd.times do
  pn, qn = gets.split.map(&:to_i)
  #p [pn, qn]

  p2q2 = pn * pn + qn * qn

  count = 0
  m = 0
  while m * m <= p2q2
    n2 = p2q2 - m * m
    n = 0
    while n * n <= n2
      m2n2 = m * m + n * n
      if (m != 0 || n != 0) &&
         (m * pn + n * qn) % m2n2 == 0 && (m * qn - n * pn) % m2n2 == 0
        count += 1
      end
      
      n += 1
    end
    m += 1
  end

  puts (count <= 4 ? 'P' : 'C')
end