Problem:
Problem A: Ginkgo Numbers We will define Ginkgo numbers and multiplication on Ginkgo numbers. A Ginkgo number is a pair < m , n > where m and n are integers. For example, <1, 1>, <-2, 1> and <-3,-1> are Ginkgo numbers. The multiplication on Ginkgo numbers is defined by < m , n > · < x , y > = < mx − ny , my + nx >. For example, <1, 1> · <-2, 1> = <-3,-1>. A Ginkgo number < m , n > is called a divisor of a Ginkgo number < p , q > if there exists a Ginkgo number < x , y > such that < m , n > · < x , y > = < p , q >. For any Ginkgo number < m , n >, Ginkgo numbers <1, 0>, <0, 1>, <-1, 0>, <0,-1>, < m , n >, <- n , m >, <- m ,- n > and < n ,- m > are divisors of < m , n >. If m 2 + n 2 > 1, these Ginkgo numbers are distinct. In other words, any Ginkgo number such that m 2 + n 2 > 1 has at least eight divisors. A Ginkgo number < m , n > is called a prime if 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.  Suppose m 2 + n 2 > 0. Then, < m , n > is a divisor of < p , q > if and only if the integer m 2 + n 2 is a common divisor of mp + nq and mq − np .  If < m , n > · < x , y > = < p , q >, then ( m 2 + n 2 )( x 2 + y 2 ) = p 2 + q 2 .  Input 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 m and n , separated by a space. They designate the Ginkgo number < m , n >. You can assume 1 < m 2 + n 2 < 20000. Output For each dataset, output a character ' P ' in a line if the Ginkgo number is a prime. Output a character ' C ' in a line otherwise. Sample Input 8
10 0
0 2
-3 0
4 2
0 -13
-4 1
-2 -1
3 -1 Output for the Sample Input C
C
P
C
C
P
P
C

Solution (Python):
C = set([i*i+j*j for i in xrange(160) for j in xrange(160)])

N = int(raw_input())
for loop in xrange(N):
    p,q = map(abs,map(int,raw_input().split()))
    pq = p*p+q*q

    cnt = 0
    for x in xrange(0,max(p,q)):
        for y in xrange(x,max(p,q)):
            xy = x*x+y*y
            if xy < 1: continue
            if pq%xy == 0 and pq/xy in C:
                cnt += 1
    print "P" if cnt == 1 else "C"

Solution (Python):
for _ in range(int(input())):
    p,q=map(int,input().split())
    c=0
    for i in range(143):
        for j in range(143):
            if (i>0 or j>0)and(j*p+i*q)%(j*j+i*i)==0 and (j*q-i*p)%(j*j+i*i)==0:c+=1
    print('P' if c<5 else 'C')

Solution (Python):
for _ in range(int(input())):
    p,q=map(int,input().split())
    c=0
    for i in range(142):
        for j in range(142):
            if (i>0 or j>0)and(j*p+i*q)%(j*j+i*i)==0 and (j*q-i*p)%(j*j+i*i)==0:c+=1
    print('P' if c<5 else 'C')

Solution (Python):
for i in range(int(input())):
    m, n = map(int, input().split())

    if m*n < 0:
        m, n = -n, m
    m = abs(m); n = abs(n)
    l = max(abs(m), abs(n))
    cnt = 0
    for p in range(l+1):
        for q in range(l+1):
            if p == 0: continue
            if (p*m + q*n) % (p**2 + q**2) < 1 and (p*n - q*m) % (p**2 + q**2) < 1:
                cnt += 1
    print("CP"[cnt == 2])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    M = 20000
    s = set()
    for i in range(int(M**0.5)+1):
        for j in range(int(M**0.5)+1):
            t = i**2+j**2
            if t > 1:
                s.add(t)

    n = I()
    ni = 0
    while ni < n:
        ni += 1
        a,b = LI()
        t = a**2 + b**2
        r = 'P'
        for c in s:
            if t % c == 0 and t // c in s:
                r = 'C'
                break

        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())

Solution (Python):


"""
Problems 1325
Problem A: Ginkgo Numbers
"""
for _ in range(int(input())):
    m, n = map(int,input().split())
    count = 0
    for p in range(142):
        for q in range(142):
            if (p > 0 or q > 0) and ((m*q + n*p) % (p*p + q*q) == 0) and ((n*q - m*p) % (p*p + q*q) == 0):
                count += 1
    if count < 5:
        print('P')
    else:
        print('C')

Solution (Python):
for i in range(int(input())):
    m, n = map(int, input().split())
    count = 0
    for p in range(142):
        for q in range(142):
            if p == q == 0:
                continue

            pq = p * p + q * q
            if pq > 20000:
                break

            if (m * p + n * q) % pq == 0 and (n * p - m * q) % pq == 0:
                count += 1

    if count < 5:
        print("P")
    else:
        print("C")

Solution (Python):
def divisor(a):
    ret = []
    for i in range(1, int(a ** 0.5) + 1):
        if not a % i:
            ret.append(i)
            ret.append(a // i)
    
    return ret

def make_lists():
    ret = [[] for i in range(20000)]

    for i in range(0, int(20000 ** 0.5) + 1):
        for j in range(0, int(20000 ** 0.5) + 1):
            if i ** 2 + j ** 2 < 20000:
                ret[i ** 2 + j ** 2].append([i, j])
    
    return ret

lists = make_lists()
ans = []

for loop in range(int(input())):
    m, n = map(int, input().split())
    C = []

    for div in divisor(m ** 2 + n ** 2):
        for l in lists[div]:
            for tmp in [-1, 1]:
                for tmp2 in [-1, 1]:
                    x, y = l[0] * tmp, l[1] * tmp2
                    if not (m * x + n * y) % (x ** 2 + y ** 2) and not (n * x - m * y) % (x ** 2 + y ** 2):
                        if [x, y] not in C:
                            C.append([x, y])

    ans.append('P' if len(C) == 8 else 'C')

[print(i) for i in ans]

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,m = LI()
    e = IR(m)
    f = [0 for i in range(n+1)]
    ans = [None for i in range(n)]
    i = m-1
    while i >= 0:
        if not f[e[i]]:
            f[e[i]] = 1
        else:
            e.pop(i)
        i -= 1
    ans[:len(e)] = e[::-1]
    k = sum(f)
    for i in range(1,n+1):
        if not f[i]:
            ans[k] = i
            k += 1
    for i in ans:
        print(i)
    return


def B():
    def mul(a,b):
        return (a[0]*b[0]-a[1]*b[1])**2+(a[0]*b[1]+a[1]*b[0])**2
    def factorize(n):
        if n < 4:
            return []
        i = 2
        res = []
        while i**2 < n:
            if n%i == 0:
                res.append(i)
            i += 1
        return res
    q = I()
    power = [i**2 for i in range(1000000)]
    f = defaultdict(lambda : 0)
    for i in power:
        f[i] = 1
    for _ in range(q):
        a,b = LI()
        k = mul((a,b),(a,b))
        fa = factorize(k)
        ans = None
        for i in fa:
            j = k//i
            s = 0
            for m in power:
                if m > i:break
                n = i-m
                if f[n]:
                    s += 1
                    break
            for m in power:
                if m > j:break
                n = i-m
                if f[n]:
                    s += 1
                    break
            if s == 2:
                ans = "C"
                break
        if ans == None:
            print("P")
        else:
            print("C")
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


def I_():
    return


def J():
    return


if __name__ == "__main__":
    B()