#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <cassert>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define MT make_tuple
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

bool dividable(P a, P b){
	int d = b.first*b.first + b.second*b.second;
	int x = a.first*b.first + a.second*b.second;
	int y = -a.first*b.second + a.second*b.first;
	if (!d || x%d || y%d) return false;

	return true;
}

int main(){
	vector<P> ginkgo;
	for (int i = -150; i <= 150; ++i){
		for (int j = -150; j <= 150; ++j){
			if (i*i + j*j < 20000) ginkgo.push_back(MP(i, j));
		}
	}

	int n;
	cin >> n;
	while (n--){
		int m, n;
		cin >> m >> n;
		P mn = MP(m, n);
		int cnt = 0;
		for (auto p : ginkgo){
			cnt += dividable(mn, p);
		}
		cout << (cnt == 8 ? 'P' : 'C') << endl;
	}

	return 0;
}