
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}



signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  bool d[21000]={};
  int a=0,b=0;
  while(a*a+b*b<20000){
    int s=a*a+b*b;
    int t=s;
    if(t>0)
    while(t<20000){
      d[t]=true;
      t+=s;
    }
    a++;
    if(a*a+b*b>20000){
      b++;
      a=0;
    }
  }


  int t;
  cin>>t;
  while(t--){
    int p,q;
    cin>>p>>q;
    int m=-200,n=-200;
    int sum=0;
    while(true){
      int s=m*m+n*n;
      int a=m*p+n*q;
      int b=m*q-n*p;
      if(s&&a%s==0&&b%s==0){
        if((p*p+q*q)%s==0)
        sum+=d[(p*p+q*q)/s];
      }
      m++;
      if(m==200){
        if(n==200) break;
        n++;
        m=-200;
      }
    }

    cout<<(sum>8?'C':'P')<<endl;
  }

}

