#include<iostream>
#include<utility>
#include<set>
#include<cmath>
using namespace std;
typedef pair<int, int> P;

int dm[2] = {-1, 1}, dn[2] = {-1, 1};

void solve() {
    int p, q;
    cin >> p >> q;
    set<P> S;
    for (int i = 1; i * i <= p * p + q * q; i++) {
        // i=m^2+n^2
        for (int m = 0; m * m <= i; m++) {
            int n = sqrt(i - m * m);
            if (m * m + n * n != i) continue;
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    int now_m = dm[j] * m;
                    int now_n = dn[k] * n;
                    int number1 = now_m * p + now_n * q;
                    int number2 = now_m * q - now_n * p;
                    if (number1 % i == 0 && number2 % i == 0) {
                        S.insert(P(now_m, now_n));
                    }
                }
            }
        }
        if (i * i == p * q) continue;
        int now_i = (p * p + q * q) / i;
        for (int m = 0; m * m <= now_i; m++) {
            int n = sqrt(now_i - m * m);
            if (m * m + n * n != now_i) continue;
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    int now_m = dm[j] * m;
                    int now_n = dn[k] * n;
                    int number1 = now_m * p + now_n * q;
                    int number2 = now_m * q - now_n * p;
                    if (number1 % now_i == 0 && number2 % now_i == 0) {
                        S.insert(P(now_m, now_n));
                    }
                }
            }
        }
    }
    if (S.size() == 8) cout << 'P' << endl;
    else cout << 'C' << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}
