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

int t,m,n,ok,s;

void solve(){
    ok=0;
    for (int i=0;i*i<=m*m+n*n;++i){
        for (int j=i;i*i+j*j<=m*m+n*n;++j){
            s=i*i+j*j;
            if (s<2||(i==abs(m)&&j==abs(n))) continue;
            if ((m*m+n*n)%s!=0) continue;
            if ((m*i+n*j)%s==0&&(n*i-m*j)%s==0) ok=1;
            if ((-m*i+n*j)%s==0&&(-n*i-m*j)%s==0) ok=1;
        }
    }
    cout << (ok?'C':'P') << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> t;
    for (;t--;){
        cin >> m >> n;
        if (abs(n)<abs(m)) swap(m,n);
        solve();
    }
}
