1.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 960 Gaussian Primes
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=11&problem=901&mosmsg=Submission+received+with+ID+7499171
*
* @author Stefan Gohlke
* @version 1.0, 10/21/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.148
*/

package gaussianPrime_acc;

import java.util.Scanner;

public class Main {

public static void main (String[] args)
{
gaussianPrime();
}

public static void gaussianPrime()
{
Scanner scanner = new Scanner(System.in);
long n = 0;
n = scanner.nextLong();

while (scanner.hasNextLong())
{
//for (int i =0; i < n; i++)
while(scanner.hasNextLong())
{
boolean isGPrime = false;
long a= scanner.nextLong();

if(!scanner.hasNextLong()) break;

long b = scanner.nextLong();


if (a != 0 && b != 0 ) isGPrime = pruefPrim((a*a) + (b*b));
else if (a == 0) isGPrime = pruefPrim(Math.abs(b)) && Math.abs(b) % 4 == 3;
else if (b == 0) isGPrime = pruefPrim(Math.abs(a)) && Math.abs(a) % 4 == 3;

if (isGPrime) System.out.println("P");
else System.out.println("C");


}

}
}

public static boolean pruefPrim(long zuPruefendeZahl)
{
for (long i = 2; i<= Math.sqrt(zuPruefendeZahl); i++)
{
if (zuPruefendeZahl%i == 0) return false;
}
return true;
}
}