#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
int SQ(int x){
	return sqrt(x+1e-9);
}
char prime(){
	int p,q;
	cin>>p>>q;
	int t=p*p+q*q;
	for(int x=-SQ(t);x<=SQ(t);x++){
		for(int y=-SQ(t-x*x);y<=SQ(t-x*x);y++){
			if(x*x+y*y<=1) continue;
			int f=x*x+y*y;
			if(t%f) continue;
			int g=t/f;
			for(int a=-SQ(g);a<=SQ(g);a++){
				for(int b=-SQ(g-a*a);b<=SQ(g-a*a);b++){
					if(a*a+b*b<=1) continue;
					if(a*x-b*y==p&&a*y+b*x==q){
						return 'C';
					}
				}
			}
		}
	}
	return 'P';
}
int main(){
	int n;
	cin>>n;
	rep(tt,n) cout<<prime()<<endl;
}