#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
bool Solve(){
	int n,m;
	cin>>n>>m;
	int ans=n*n+m*m;
	for(int i=0;i*i<ans;i++){
		for(int j=i;i*i+j*j<ans;j++){
			if(i==0&&j==0||i==0&&j==1){
				continue;
			}
			if(ans%(i*i+j*j)==0){
				return false;
			}
		}
	}
	return true;
}
int main(){
	int test;
	cin>>test;
	while(test--){
		if(Solve()){
			cout<<"P"<<endl;
		}
		else{
			cout<<"C"<<endl;
		}
	}
	return 0;
}