#include <stdio.h>
int main(void)
{
    int N;
    while (~scanf("%d", &N)) {
        while (N--) {
            int p, q, n, m, c;
            scanf("%d%d", &p, &q);
            c=0;
            for(n=0;n<143;++n) for(m=0;m<143;++m) if (m>0 || n>0) {
                int t=m*m+n*n, a=m*p+n*q, b=m*q-n*p;
                if (a%t==0 && b%t==0) ++c;
            }
            puts(c>4?"C":"P");
        }
    }
    
    return 0;
}