#include <bits/stdc++.h>
using namespace std;
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    int m, n;
    cin >> m >> n;
    int s = m * m + n * n;
    bool prime = true;
    int a = sqrt(s - 1);
    for (int j = - a; j <= a; j++){
      int b = sqrt(s - j * j - 1);
      for (int k = - b; k <= b; k++){
        int t = j * j + k * k;
        if (abs(t) > 1){
          if ((j * m + k * n) % (j * j + k * k) == 0 && (j * n - k * m) % (j * j + k * k) == 0){
            prime = false;
          }
        }
      }
    }
    if (prime){
      cout << 'P' << endl;
    } else {
      cout << 'C' << endl;
    }
  }
}
