#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

vector<int>P;
int p[20005];

void init()
{
  p[0] = p[1] = 1;
  for(int i=2;i<20005;i++)
    for(int j=i+i;j<20005;j+=i) p[j] = 1;
  for(int i=3;i<20005;i++){
    if(p[i] == 0 && (i%4 == 3)) P.push_back(i);
  }
}

int fanc1(int x)
{
  return x%4 == 1 && p[x] == 0;
}

int fanc2(int x)
{
  rep(i, P.size()) if(x == P[i]*P[i]) return 1;
  return 0;
}

int main()
{
  init();
  int N;
  cin >> N;
  rep(i, N){
    int m, n;
    cin >> m >> n;
    int x = m*m + n*n;
    if(x == 2 || fanc1(x) || fanc2(x)) cout << "P\n";
    else cout << "C\n";
  }
  return 0;
}