Ginkgo Numbers#5412
We will define Ginkgo numbers and multiplication on Ginkgo numbers.
A Ginkgo number is a pair <m, n> where and are integers. For example, <1, 1>, <-2, 1> and <-3, -1> are Ginkgo numbers.
The multiplication on Ginkgo numbers is defined by <m, n> \cdot <x, y> = <mx-ny, my+nx>.
For example, <1, 1> \cdot <-2, 1> = <-3, -1>.
A Ginkgo number <m, n> is called a divisor of a Ginkgo number <p, q> if there exists a Ginkgo number <x, y> such that <m, n> \cdot <x, y> = <p, q>.
For any Ginkgo number <m, n>, Ginkgo numbers <1, 0>, <0, 1>, <-1, 0>, <0, -1>, <m, n>, <-n, m>, <-m, -n> and <n, -m> are divisors of <m, n>. If m^2+n^2 > 1, these Ginkgo numbers are distinct. In other words, any Ginkgo number such that m^2 + n^2 > 1 has at least eight divisors.
A Ginkgo number <m, n> is called a prime if m^2+n^2 > 1 and it has exactly eight divisors. Your mission is to check whether a given Ginkgo number is a prime or not.
The following two facts might be useful to check whether a Ginkgo number is a divisor of another Ginkgo number.
Suppose m^2 + n^2 > 0. Then, <m, n> is a divisor of <p, q> if and only if the integer m^2 + n^2 is a common divisor of mp + nq and mq - np.
If <m, n> \cdot <x, y> = <p, q>, then (m^2 + n^2)(x^2 + y^2) = p^2 + q^2.
The first line of the input contains a single integer, which is the number of datasets. The rest of the input is a sequence of datasets. Each dataset is a line containing two integers and , separated by a space. They designate the Ginkgo number <m, n>. You can assume 1 < m^2 + n^2 < 20000.
For each dataset, output a character 'P' in a line if the Ginkgo number is a prime. Output a character 'C' in a line otherwise.
Example 1