Bank Numbers

A bank number is an ordered pair of integers $(m, n)$. For example, $(1, 1)$, $(-2, 1)$, and $(-3, -1)$ are bank numbers.

Multiplication of bank numbers is defined by $(m, n) \cdot (x, y) = (mx - ny,\; my + nx)$. For example, $(1, 1) \cdot (-2, 1) = (-3, -1)$.

If some bank number $(x, y)$ satisfies $(m, n) \cdot (x, y) = (p, q)$, then $(m, n)$ is called a divisor of the bank number $(p, q)$.

For any bank number $(m, n)$, each of $(1, 0)$, $(0, 1)$, $(-1, 0)$, $(0, -1)$, $(m, n)$, $(-n, m)$, $(-m, -n)$, $(n, -m)$ is a divisor of $(m, n)$. If $m^2 + n^2 > 1$, these eight bank numbers are all distinct, so every bank number with $m^2 + n^2 > 1$ has at least eight divisors.

A bank number $(m, n)$ with $m^2 + n^2 > 1$ is called prime if it has exactly eight divisors.

Given a bank number, write a program that decides whether it is prime.

The first line contains the number of test cases. Each test case is a single line containing $m$ and $n$ of a bank number $(m, n)$, separated by a space. ($1 < m^2 + n^2 < 20000$)

For each test case, print P on its own line if the given bank number is prime, and C otherwise.

When $m^2 + n^2 > 0$, if $m^2 + n^2$ is a common divisor of $mp + nq$ and $mq - np$, then $(m, n)$ is a divisor of $(p, q)$, and the converse also holds.

Moreover, if $(m, n) \cdot (x, y) = (p, q)$, then $(m^2 + n^2)(x^2 + y^2) = p^2 + q^2$.