#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int tt;
int m,n;
bool prime[20001];
int pt[20001];
bool ok[20001];
int main(void){
	scanf("%d",&tt);
	memset(pt,false,sizeof(pt));
	for(int i=0;i*i<=20000;i++){
		for(int j=i;j*j+i*i<=20000;j++){
			pt[i*i+j*j]=true;
		}
	}
	for(int cc=0;cc<tt;cc++){
		scanf("%d %d",&m,&n);
		bool flag=true;
		for(int i=0;i*i<=m*m+n*n;i++){
			if(!flag)break;
			for(int j=i;j*j+i*i<=m*m+n*n;j++){
				if(i*i+j*j<=1)continue;
				if(!flag)break;
				if((m*m+n*n)%(i*i+j*j)!=0)continue;
				if(!pt[(m*m+n*n)/(i*i+j*j)])continue;
				if(abs(m)==abs(i) && abs(n)==abs(j))continue;
				if(abs(n)==abs(i) && abs(m)==abs(j))continue;
				int k=i*i+j*j;
				int d=i*m+j*n;
				if(abs(d)%k==0)flag=false;
				d=i*n-j*m;
				if(abs(d)%k==0)flag=false;
				i=-i;
				d=i*m+j*n;
				if(abs(d)%k==0)flag=false;
				d=i*n-j*m;
				if(abs(d)%k==0)flag=false;
				j=-j;
				d=i*m+j*n;
				if(abs(d)%k==0)flag=false;
				d=i*n-j*m;
				if(abs(d)%k==0)flag=false;
				i=-i;
				d=i*m+j*n;
				if(abs(d)%k==0)flag=false;
				d=i*n-j*m;
				if(abs(d)%k==0)flag=false;
				j=-j;
				//if(!flag)printf("%d %d\n",i,j);
			}
		}
		printf("%c\n",flag?'P':'C');
	}
	return 0;
}