#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX/10;

int main() {
	int N;
	cin >> N;
	REP(_, N) {
		int p, q;
		cin >> p >> q;
		bool ok = true;
		for(int m = -4000; m <= 4000; m++) {
			for(int n = -4000; n <= 4000; n++) {
				int a = m*m+n*n;
				if(a <= 1 || 20000 <= a) {
					continue;
				}
				int b = m*p+n*q;
				int c = m*q-n*p;
				if(b%a == 0 && c%a == 0) {
					if((m == p && n == q) || (-n == p && m == q) || (-m == p && -n == q) || (n == p && -m == q)) {
						continue;
					}
					ok = false;
					goto show;
				}
			}
		}
		show:
		cout << (ok ? 'P' : 'C') << endl;
	}
	return 0;
}