#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#define f first
#define s second

using namespace std;

typedef pair<int,int> P;

int gcd(int a,int b){
  if(b==0)return a;
  return gcd(b,a%b);
}

int main(void){

  int t;
  cin >> t;

  while(t--){
    int p,q;
    cin >> p >> q;
    int tmp=p*p+q*q,cnt=0;

    for(int n=0;n*n<=tmp;n++){
      for(int m=0;m*m<=tmp;m++){
        if(m*m+n*n<1)continue;
        int res=gcd(m*p+n*q,m*q-n*p);
        if((m*p+n*q)%(m*m+n*n)==0 && (m*q-n*p)%(m*m+n*n)==0)cnt++;
      }
    }

    if(cnt*2<=8)cout << "P" << endl;
    else cout << "C" << endl;
  }
  return 0;
}