#include <iostream>
#include <vector>
#include <complex>
#include <cstdlib>

using namespace std;

const int N = 20000;

vector<bool> p;

void init(){
    p.assign(N, true); p[0] = p[1] = false;
    for(int i=2; i<N; ++i)if(p[i]){
        for(int j=i<<1; j<N; j+=i)p[j] = false;
    }
}

bool solve(int m, int n){ //http://en.wikipedia.org/wiki/Gaussian_integer
    complex<int> g(abs(m), abs(n));
    return (g.real() == 0 && g.imag() % 4 == 3 && p[g.imag()]) ||
           (g.imag() == 0 && g.real() % 4 == 3 && p[g.real()]) ||
           norm(g) == 2 || (norm(g) % 4 == 1 && p[norm(g)]);
}

int main(){
    init();
    int T;
    cin >> T;
    while(T--){
        int m, n;
        cin >> m >> n;
        cout << (solve(m, n)? 'P': 'C') << '\n';
    }
    return 0;
}