#include <iostream>
using namespace std;

bool isPrime(int x) {
	for(int i=2 ; i * i <= x ; i++ ) {
		if( x % i == 0 ) return false;
	}
	return true;
}

bool isGaussianPrime(int a, int b) {
	if (a < 0) a = -a;
	if (b < 0) b = -b;
	if (a == 0) return b % 4 == 3 && isPrime(b);
	if (b == 0) return a % 4 == 3 && isPrime(a);
	return isPrime(a*a + b*b);
}

int main(){
	int n;
	cin >> n;
	for(int t=0 ; t < n ; t++ ){
		int a, b;
		cin >> a >> b;
		cout << (isGaussianPrime(a, b)? "P" : "C") << endl;
	}
}