Problems
Ginkgo Numbers
Ginkgo Numbers
We will de ne Ginkgo numbers and multiplication on Ginkgo numbers.
A \textbf{Ginkgo number} is a pair <\textbf{m}, \textbf{n}> where \textbf{m} and \textbf{n} are integers. For example, <\textbf{1}, \textbf{1}>, <\textbf{-2}, \textbf{1}> and <\textbf{-3}, \textbf{-1}> are Ginkgo numbers.
The multiplication on Ginkgo numbers is de ned by <\textbf{m}, \textbf{n}>\textbf{·}<\textbf{x}, \textbf{y}> = <\textbf{mx-ny}, \textbf{my+nx}>.
For example, <\textbf{1}, \textbf{1}>\textbf{·}<\textbf{-2}, \textbf{1}> = <\textbf{-3}, \textbf{-1}>.
A Ginkgo number <\textbf{m}, \textbf{n}> is called a divisor of a Ginkgo number <\textbf{p}, \textbf{q}> if there exists a Ginkgo number <\textbf{x}, \textbf{y}> such that <\textbf{m}, \textbf{n}>\textbf{·}<\textbf{x}, \textbf{y}> = <\textbf{p}, \textbf{q}>.
For any Ginkgo number <\textbf{m}, \textbf{n}>, Ginkgo numbers <\textbf{1}, \textbf{0}>, <\textbf{0}, \textbf{1}>, <\textbf{-1}, \textbf{0}>, <\textbf{0}, \textbf{-1}>, <\textbf{m}, \textbf{n}>, <\textbf{-n}, \textbf{m}>, <\textbf{-m}, \textbf{-n}> and <\textbf{n}, \textbf{-m}> are divisors of <\textbf{m}, \textbf{n}>. If \textbf{m^2+n^2} > \textbf{1}, these Ginkgo numbers are distinct. In other words, any Ginkgo number such that \textbf{m^2 + n^2} > \textbf{1} has at least eight divisors.
A Ginkgo number <\textbf{m}, \textbf{n}> is called a prime if \textbf{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.
\begin{itemize}
\item Suppose \textbf{m^2 + n^2} > \textbf{0}. Then, <\textbf{m}, \textbf{n}> is a divisor of <\textbf{p}, \textbf{q}> if and only if the integer \textbf{m^2 + n^2} is a common divisor of \textbf{mp + nq} and \textbf{mq - np}.
\item If <\textbf{m}, \textbf{n}>\textbf{·}<\textbf{x}, \textbf{y}> = <\textbf{p}, \textbf{q}>, then \textbf{(m^2 + n^2)(x^2 + y^2) = p^2 + q^2}.
\end{itemize}
\InputFile
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 \textbf{m} and \textbf{n}, separated by a space. They designate the Ginkgo number <\textbf{m}, \textbf{n}>. You can assume \textbf{1} < \textbf{m^2 + n^2} < \textbf{20000}.
\OutputFile
For each dataset, output a character '\textbf{P}' in a line if the Ginkgo number is a prime. Output a character '\textbf{C}' in a line otherwise.
Input example #1
8 10 0 0 2 -3 0 4 2 0 -13 -4 1 -2 -1 3 -1
Output example #1
C C P C C P P C