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.