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

int main(){
  int d,m,n,L=141,ans;
  cin>>d;
  while(d--){
    cin>>m>>n;
    ans=0;
    for(int i=-L;i<L;i++)
      for(int j=-L;j<L;j++){
	if(!i&&!j)continue;
	int a=i*i+j*j;
	if(!((i*m+j*n)%a)&&!((i*n-j*m)%a))ans++;
      }
    if(ans==8)cout<<"P"<<endl;
    else cout<<"C"<<endl;
  }
  return 0;
}