1. C, Andreas Kunft

/*
 * ACM Programming Contest
 * Problem: 960
 * Status: Accepted
 * Language: JAVA
 * Runtime: 0.070
 * Date: 2009-04-01 12:39:06
 * Author: Andreas Kunft
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
public static void main(String... args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
reader.readLine();
for (String line = reader.readLine(); line != null; line = reader.readLine())
{
String[] number = line.split(" ");
if (number.length == 2)
{
int real = Integer.parseInt(number[0]);
int img = Integer.parseInt(number[1]);

if (real != 0 && img != 0)
{
if (isPrime(real * real + img * img))
System.out.println('P');
else
System.out.println('C');
}

if (real == 0 && img != 0)
{
if (isPrime(Math.abs(img)) && Math.abs(img) % 4 == 3)
System.out.println('P');
else
System.out.println('C');
}

if (real != 0 && img == 0)
{
if (isPrime(Math.abs(real)) && Math.abs(real) % 4 == 3)
System.out.println('P');
else
System.out.println('C');
}
}
}
}

private static boolean isPrime(int n)
{
if (n < 2)
return false;
if (n == 2)
return true;
if (n % 2 == 0)
return false;
int sqrt = (int) Math.sqrt(n);
for (int i = 3; i <= sqrt; i += 2)
if (n % i == 0)
return false;
return true;
}
}