#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

//common
typedef long long ll;

#define BR "\n"
#define ALL(c) (c).begin(),(c).end()
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

//config
//#undef NDEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//debug
#ifdef NDEBUG
#define DUMP(x)
#define DUMPLN(x)
#define DEBUG(x)
#define DEBUGLN(x)
#define LINE()
#define LINELN()
#define CHECK(exp,act)
#define STOP(e)
#else
#define DUMP(x)  cerr << #x << " = " << (x)
#define DUMPLN(x)  DUMP(x) <<endl
#define DEBUG(x) DUMP(x) << LINE() << " " << __FILE__
#define DEBUGLN(x) DEBUG(x)<<endl
#define LINE()    cerr<< " (L" << __LINE__ << ")"
#define LINELN()    LINE()<<endl
#define CHECK(exp,act)  if(exp!=act){DUMPLN(exp);DEBUGLN(act);}
#define STOP(e)  CHECK(e,true);if(!(e)) exit(1);
#endif

template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
	}
	return ss.str();
}

template<class T> inline string toString(const vector<vector<T> >& map) {
	stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss<< p.first<<":" << p.second<<" ";
	return ss.str();
}

//ind -> V から V->ind (注:単射)
template<typename T>
map<T,int> rev(const vector<T>& xs){
	map<T,int> rev;
	REP(i,(int)xs.size())rev.insert(make_pair(xs[i],i));
	return rev;
}

template<typename T,typename V> inline T mod(T v,V MOD){
	return (v%MOD+MOD)%MOD;
}
int INF=1<<28;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


struct Edge{
	int  from,to,d,c;
	Edge(int u,int v,int d,int c):from(u),to(v),d(d),c(c){};
};
struct Task{
    int prev,pos,d;
    Task(int prev,int pos,int d)
        :prev(prev),pos(pos),d(d){};
    bool operator>(const Task& r) const{
        return d>r.d;
    }
};
typedef vector<vector<Edge> > Graph;

vector<int> dijkstra(const Graph& g,const int s,vector<int>& prev){
        const int V=g.size();
        vector<int> d(V,INF);d[s]=0;
        fill(ALL(prev), -2);
        priority_queue<Task,vector<Task>,greater<Task> > que;
        que.push(Task(-1,s,0));
        while(!que.empty()){
            Task task=que.top();que.pop();
            //if(prev[task.pos]!=-2)continue;
            if(d[task.pos]<task.d)continue;
            prev[task.pos]=task.prev;
            EACH(e,g[task.pos]){
                if(d[e->to]>d[e->from]+e->d){
                    d[e->to]=d[e->from]+e->d;que.push(Task(e->from,e->to,d[e->to]));
                }
            }   
        }
        return d;
    }
    vector<int> dijkstra(const Graph& g,const int s){
        vector<int> prev(g.size());return dijkstra(g,s,prev);
    }

typedef int T;
T gcd(T a,T b){return b==0 ? a : gcd(b,a%b);}
	
class Main{
public:	
	int N,M;
	vector<vector<Edge>> es;
	void run(){
		int N;cin >>N;
		REP(i,N){
			int p,q;cin >> p >>q;
			int pq=p*p+q*q;
			
			bool prime=true;

			REP(m,pq+1)REP(n,pq+1){
				int mn=m*m+n*n;
				if(mn>pq)break;
				if(mn<=1 || mn==pq)continue;
				if(pq%mn==0){
					prime=false;
				}
			}
			cout <<(prime?"P":"C")<<endl;
		}
	}
};

int main(){
	Main().run();
	return 0;
}

Measured memory_bytes: 1156