#include <bits/stdc++.h>
using namespace std;

bool isPrime(int m, int n) {
  int r = m*m + n*n;
  if(r > 1); else return false;
  int cnt = 0;
  for(int a = 0; a*a <= r; a = -a + (a <= 0)) {
    for(int b = 0; a*a + b*b <= r; b = -b + (b <= 0)) {
      int c = a*a + b*b;
      if(c > 0); else continue;
      if((a*m + b*n) % c == 0 && 
         (a*n - b*m) % c == 0) {
        ++cnt;
      }
    }
  }
  return cnt == 8;
}

int main() {
  int T; cin >> T;
  while(T--) {
    int m, n; cin >> m >> n;
    cout << (isPrime(m, n) ? "P" : "C") << endl;
  }
  return 0;
}