n = gets.to_i
n.times do
    p, q = gets.split.map(&:to_i)
    ss = p * p + q * q
    count = 0
    done = Array.new
    2.upto(ss) do |s|
        0.upto(Math.sqrt(s)) do |u|
            v = Math.sqrt(s - u**2).to_i
            next if u**2 + v**2 != s
            if (p * u + q * v) % s == 0 && (q * u - p * v) % s == 0
                if !done.include?([u,v])
                    done.push([u,v])
                    count += 1
                end
            end
            u = -u
            if (p * u + q * v) % s == 0 && (q * u - p * v) % s == 0
                if !done.include?([u,v])
                    done.push([u,v])
                    count += 1
                end
            end
            v = -v
            if (p * u + q * v) % s == 0 && (q * u - p * v) % s == 0
                if !done.include?([u,v])
                    done.push([u,v])
                    count += 1
                end
            end
            u = -u
            if (p * u + q * v) % s == 0 && (q * u - p * v) % s == 0
                if !done.include?([u,v])
                    done.push([u,v])
                    count += 1
                end
            end
        end
    end
    puts count == 4 ? "P" : "C"
end