#include<iostream>
using namespace std;
int calc(int m,int n,int p,int q){
  if( (m==1 && n==0) || (m==0 && n==1) || (m==-1 && n==0) ||
      (m==0 && n==-1) || (m==p && n==q) || (m==-q && n==p) ||
      (m==-p && n==-q) || (m==q && n==-p) || (m==0 && n==0)){
    return 0;
  }
    if( (m*p+n*q) %(m*m+n*n)==0){
      if( (-p*n+m*q)%(m*m+n*n)==0){
	//cout << "baka" << endl;
	//cout << "m " << m<<"n "<<n<< endl;
	return 1;//割り切れる
      }
    }
  //cout << "p " << m<<"q "<<n<< endl;
  return 0;//割り切れない
}

int main(){
  int a,m,n;
  bool flag=0;
  cin>>a;
  for(int i=0;i<a;i++){
    cin>>m>>n;
    flag=0;
    for(int j=-500;j<500;j++){
      for(int k=-500;k<500;k++){
	if(calc(j,k,m,n) == 1){
	  flag=1;
	  break;
	}
      }
      if(flag==1) break;
    }
    if(flag==1){
      cout<<"C"<<endl;
    }else{
      cout<<"P"<<endl;
    }
  }
  return 0;
}