#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <sstream>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define SORT(x) sort((x).begin(), (x).end())
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

int main(){
	int q;
	int m, n;
	scanf("%d", &q);
	rep(i,q){
		scanf("%d%d", &m, &n);
		if(m < 0) m *= -1;
		if(n < 0) n *= -1;
		int sum = m*m+n*n;
		bool ok = false;
		rep(j,200){
			if(j*j > sum) break;
			rep(k,200){
				if((j==0&&k==1)||(j==1&&k==0)||(j==m&&k==n)||(j==n&&k==m)) continue;
				if(j*j+k*k > sum) break;
				rep(u,200){
					if((j*j+k*k)*u*u > sum) break;
					rep(v,200){
						if((j*j+k*k)*(u*u+v*v) == sum){
							//cout << j << " " << k << " " << u << " " << v << endl;
							printf("C\n");
							ok = true;
							break;
						}
					}
					if(ok) break;
				}
				if(ok) break;
			}
			if(ok) break;
		}
		if(!ok) printf("P\n");
	}
}