1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: Brute Force
* Problem: 960 Gaussian Primes
* Accepted: 1.828
* @author Evgeni Pavlidis
*
*/
import java.io.*;
import java.util.*;

class Main {

private static boolean isPrime(long n)
{
if(n < 2)
return false;

if(n % 2 == 0)
return false;

int squareRoot = (int)Math.sqrt(n);
for(int i = 3; i <= squareRoot; i += 2)
if(n % i == 0)
return false;

return true;
}

private static boolean isGaussianPrime(long a, long b)
{
if(a == 0 && isPrime(Math.abs(b)) && Math.abs(b) % 4 == 3)
return true;

if(b == 0 && isPrime(Math.abs(a)) && Math.abs(a) % 4 == 3)
return true;

if(isPrime(a*a+b*b))
return true;

return false;
}

public static void main(String...args)
{
Scanner sc = new Scanner(System.in);

int testCases = sc.nextInt();
for(int tc = 0; tc < testCases; tc++)
if(isGaussianPrime(sc.nextInt(), sc.nextInt()))
System.out.println("P");
else
System.out.println("C");
}
}