#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int t;

    int ans;
    int n,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);
        if(n*n+m*m<=1){
            printf("C\n");
            continue;
        }
        int x=sqrt(m*m+n*n+0.5);
        ans=0;

        for(int i=-x;i<=x;i++){
            for(int j=-x;j<=x;j++){
                int p=i*m+j*n;
                int q=i*n-j*m;
                int z=i*i+j*j;
                if(z&&p%z==0&&q%z==0){
                    ans++;
                }
            }
        }
        if(ans==8){
            printf("P\n");
        }
        else{
            printf("C\n");
        }
    }
    return 0;
}