#include<iostream>
#include<stdio.h>
using namespace std;

int T;
int p,q;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&p,&q);
        int ans=0;
        for(int m=-200;m<200;m++){
            for(int n=-200;n<200;n++){
                int l=m*m+n*n;

                if(l>0){
                    if( ( (m*p+n*q) % l == 0) && ((m*q-n*p) % l == 0) ){
                        ans++;
                    }
                }
            }
        }
        if(ans==8){
            printf("P\n");
        }
        else{
            printf("C\n");
        }
    }
    return 0;
}