题目链接

传送门

Description

Ginkgo数是指一种由整数组成的二元组(m,n),其中m和n都是整数。例如,(1,1),(-2,1)和(-3,-1)都是Ginkgo数。Ginkgo数的乘法被定义为(m,n)?(x,y)=(mx-ny,my+nx)。例如,(1,1)?(-2,1)=(-3,-1)。一个Ginkgo数(m,n)被认为是一个Ginkgo数(p,q)的约数,则要存在一个Ginkgo数(x,y)使得(m,n)?(x,y)=(p,q)。对于任何的Ginkgo数(m,n),它都至少有(1,0),(0,1),(-1,0),(0,-1),(m,n),(-n,m),(-m,-n)和(n,-m)作为它的约数。当m^2+n^2>1时,至少有8个不同的Ginkgo数作为它的约数。一个Ginkgo数被认为是质数,则要有m^2+n^2>1且它恰好含有8个不同的约数。你的任务就是判断给定的Ginkgo数是不是质数。以下两个结论或许能帮助你完成上述任务:若m^2+n^2>0,则(m,n)是(p,q)的约数当且仅当m^2+n^2是mp+nq和mq-np的公约数。如果(m,n)?(x,y)=(p,q),那么(m^2+n^2)(x^2+y^2)=p^2+q^2。

Input

第一行一个正整数T,表示有T组数据。
每组数据占一行,包含两个整数m和n,表示一个Ginkgo数(m,n)。你可以认为1<m^2+n^2<20000。

Output

对于每组数据输出一行,如果给定的Ginkgo数是质数则输出‘P’,否则输出‘C’。(不含引号)

Sample Input

8
10 0
0 2
-3 0
4 2
0 -13
-4 1
-2 -1
3 -1

Sample Output

C
C
P
C
C
P
P
C

题解

输入这两个数我们叫做$p$,$q$,$n$,$m$是我们要的答案
发现$n$,$m$的范围并不大 我们直接枚举就行了
枚举的时候注意特判掉$n^2+m^2=0$的情况
然后直接根据第一个条件判断是不是$mp+nq$,$mq-np$的公因数就行了

代码