我们定义银杏数（Ginkgo numbers）以及银杏数上的乘法。

一个银杏数是一个二元组 $\langle m, n \rangle$，其中 $m$ 和 $n$ 是整数。例如，$\langle 1, 1 \rangle$、$\langle -2, 1 \rangle$ 和 $\langle -3, -1 \rangle$ 都是银杏数。

银杏数上的乘法定义为 $\langle m, n \rangle \cdot \langle x, y \rangle = \langle mx - ny, my + nx \rangle$。例如，$\langle 1, 1 \rangle \cdot \langle -2, 1 \rangle = \langle -3, -1 \rangle$。

如果存在一个银杏数 $\langle x, y \rangle$ 满足 $\langle m, n \rangle \cdot \langle x, y \rangle = \langle p, q \rangle$，则称银杏数 $\langle m, n \rangle$ 是银杏数 $\langle p, q \rangle$ 的约数。

对于任意银杏数 $\langle m, n \rangle$，银杏数 $\langle 1, 0 \rangle$、$\langle 0, 1 \rangle$、$\langle -1, 0 \rangle$、$\langle 0, -1 \rangle$、$\langle m, n \rangle$、$\langle -n, m \rangle$、$\langle -m, -n \rangle$ 和 $\langle n, -m \rangle$ 都是 $\langle m, n \rangle$ 的约数。如果 $m^2+n^2 > 1$，这些银杏数是互不相同的。换句话说，任何满足 $m^2 + n^2 > 1$ 的银杏数都至少有八个约数。

如果一个银杏数 $\langle m, n \rangle$ 满足 $m^2 + n^2 > 1$ 且恰好有八个约数，则称其为素数。你的任务是判断给定的银杏数是否为素数。

以下两个事实可能对判断一个银杏数是否为另一个银杏数的约数有所帮助：

• 假设 $m^2 + n^2 > 0$。那么，$\langle m, n \rangle$ 是 $\langle p, q \rangle$ 的约数当且仅当整数 $m^2 + n^2$ 是 $mp + nq$ 和 $mq - np$ 的公约数。
• 如果 $\langle m, n \rangle \cdot \langle x, y \rangle = \langle p, q \rangle$，那么 $(m^2 + n^2)(x^2 + y^2) = p^2 + q^2$。

输入格式

输入的第一行包含一个整数，表示测试数据的组数。

接下来的输入是测试数据序列。每组测试数据占一行，包含两个由空格隔开的整数 $m$ 和 $n$。它们表示银杏数 $\langle m, n \rangle$。你可以认为 $1 < m^2 + n^2 < 20000$。

输出格式

对于每组测试数据，如果该银杏数是素数，则在一行中输出字符 P。否则，在一行中输出字符 C。

样例

输入样例 1

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

输出样例 1

C
C
P
C
C
P
P
C