#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

bool issq(int x) { int y = (int)round(sqrt(x)); return y * y == x; }

pii mult(pii a, pii b) {
	return {a.first * b.first - a.second * b.second, a.first * b.second + a.second * b.first};
}

int multeq(int a, int b, int c, int d, int e, int f) {
	pii t = {e, f};
	if (mult({a, b}, {c, d}) == t || mult({a, -b}, {c, d}) == t || mult({a, b}, {c, -d}) == t || mult({a, -b}, {c, -d}) == t) return true;
	return false;
}

bool ok(int m, int n, int i, int j) {
	int iup = floor(sqrt(i)), jup = floor(sqrt(j));
	for (int ii = -iup; ii <= iup; ii++) if (issq(i - ii * ii)) {
		int a = ii, b = (int)round(sqrt(i - ii * ii)); // actually (a, -b) and (a, b)
		for (int jj = -jup; jj <= jup; jj++) if (issq(j - jj * jj)) {
			int c = jj, d = (int)round(sqrt(j - jj * jj));
			if (multeq(a, b, c, d, m, n))
				return true;
		}
	}
	return false;
}

void solve() {
	int m, n; cin >> m >> n;
	int g = m * m + n * n;
	for (int i = 2; i * i <= g; i++) if (g % i == 0) {
		if (ok(m, n, i, g / i)) {
			cout << "C" << endl;
			return;
		}
	}
	cout << "P" << endl;
}

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);

	int n; cin >> n;
	rep(i, 0, n) solve();
}

