#include <iostream>
using namespace std;

typedef long long ll;

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

// Spaghetti Source
// ガウス素数判定 : http://www.prefield.com/algorithm/math/isgprime.html
bool isGaussianPrime(ll a, ll 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 T;
  cin >> T;

  while(T--){
    ll a, b;
    cin >> a >> b;
    cout << (isGaussianPrime(a, b) ? "P" : "C") << endl;
  }
}