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> &middot; <x, y> = <mx &minus; ny, my + nx>. For example, <1, 1> &middot; <-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> &middot; <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 m2+n2 > 1, these Ginkgo numbers are distinct. In other words, any Ginkgo number such that m2 + n2 > 1 has at least eight divisors.

A Ginkgo number <m, n> is called a prime if m2+n2 > 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 m2 + n2 > 0. Then, <m, n> is a divisor of <p, q> if and only if the integer m2 + n2 is a common divisor of mp + nq and mq &minus; np.

 If <m, n> &middot; <x, y> = <p, q>, then (m2 + n2)(x2 + y2) = p2 + q2.

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 < m2 + n2 < 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



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

Submission status: Wrong Answer

Solution code:
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):
    m,n = map(int,raw_input().split())
    m,n = abs(m),abs(n)
    mn = m*m+n*n

    prime = True
    for x in xrange(1,max(m,n)):
        for y in xrange(x,max(m,n)):
            xy = x*x+y*y
            if mn%xy == 0 and mn/xy in C:
                print "C"
                prime = False
                break
        if not prime: break
    else:
        print "P"

Submission status: Wrong Answer

Solution code:
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):
    m,n = map(int,raw_input().split())
    m,n = abs(m),abs(n)
    mn = m*m+n*n
    if mn < 2:
        print "C"
        continue

    prime = True
    for x in xrange(1,max(m,n)):
        for y in xrange(x,max(m,n)):
            xy = x*x+y*y
            if mn%xy == 0 and mn/xy in C:
                print "C"
                prime = False
                break
        if not prime: break
    else:
        print "P"

Submission status: Accepted

Solution code:
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"

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
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')

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#A
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

#B
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

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    B()