은행수

은행수란 두 정수 $m$과 $n$의 순서쌍 $(m, n)$이다. 예를 들어 $(1, 1)$, $(-2, 1)$, $(-3, -1)$은 모두 은행수이다.

두 은행수의 곱셈은 $(m, n) \cdot (x, y) = (mx - ny,\; my + nx)$로 정의한다. 예를 들어 $(1, 1) \cdot (-2, 1) = (-3, -1)$이다.

어떤 은행수 $(x, y)$가 $(m, n) \cdot (x, y) = (p, q)$를 만족하면, $(m, n)$을 은행수 $(p, q)$의 약수라고 한다.

임의의 은행수 $(m, n)$에 대해 $(1, 0)$, $(0, 1)$, $(-1, 0)$, $(0, -1)$, $(m, n)$, $(-n, m)$, $(-m, -n)$, $(n, -m)$은 모두 $(m, n)$의 약수이다. $m^2 + n^2 > 1$이면 이 여덟 개의 은행수는 서로 다르다. 따라서 $m^2 + n^2 > 1$인 은행수는 약수가 적어도 여덟 개이다.

$m^2 + n^2 > 1$인 은행수 $(m, n)$의 약수가 정확히 여덟 개이면, 이 수를 소수라고 부른다.

은행수가 주어졌을 때, 그 수가 소수인지 아닌지 판정하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄이며, 은행수 $(m, n)$의 $m$과 $n$이 공백으로 구분되어 주어진다. ($1 < m^2 + n^2 < 20000$)

각 테스트 케이스마다, 주어진 은행수가 소수이면 P를, 아니면 C를 한 줄에 출력한다.

$m^2 + n^2 > 0$일 때, $m^2 + n^2$이 $mp + nq$와 $mq - np$의 공약수이면 $(m, n)$은 $(p, q)$의 약수이고 그 역도 성립한다.

또한 $(m, n) \cdot (x, y) = (p, q)$이면 $(m^2 + n^2)(x^2 + y^2) = p^2 + q^2$이다.