
fun main(args: Array<String>?): Unit {
    val pairs = Array(20000){ArrayList<Pair<Int, Int>>()}
    for (i in 1 .. Math.sqrt(19999.0).toInt()) for (j in 0 .. Math.min(i, Math.sqrt(19999.0 - i * i).toInt())) {
        pairs[i * i + j * j].run{
            add(Pair(j, i))
            add(Pair(-j, i))
            add(Pair(j, -i))
            add(Pair(-j, -i))
        }
    }
    repeat(readLine()!!.trim().toInt()){
        val (m, n) = readLine()!!.trim().split(' ').map(String::toInt)
        var isPrime = true
        loop@for (i in 2 .. Math.sqrt(m * m + n * n.toDouble()).toInt()) if ((m * m + n * n) % i == 0){
            for ((x, y) in pairs[i]) {
                val s = x * x + y * y
                if ((m * x + + n * y) % s == 0 && (m * y - n * x) % s == 0) {
                    isPrime = false
                    break@loop
                }
            }
        }
        println(if (isPrime) "P" else "C")
    }
}
fun <T> T.run(func: T.() -> Unit): Unit {
    func(this)
}

