#include <iostream>
#include <cmath>
#define MAX_SQUARE 142
#define MAX 20001
using namespace std;

bool isDivisor(int p, int q, int m, int n) {
  int temp1 = m * p + n * q;
  int temp2 = m * q - n * p;
  int square = m * m + n * n;
  if (temp1 % square == 0 && temp2 % square == 0) return true;
  return false;
}

bool isPrime(int p, int q) {
  int square = p * p + q * q;
  int count = 0;
  for (int m = 0; m * m <= square; m++) {
    for (int n = 0; m * m + n * n <= square; n++) {
      if (m * m + n * n == 0) continue;

      if (isDivisor(p, q, m, n)) {
	count++;
      }

      if (m != 0 && isDivisor(p, q, -m, n)) {
	count++;
      }

      if (n != 0 && isDivisor(p, q, m, -n)) {
	count++;
      }

      if (m != 0 && n != 0 && isDivisor(p, q, -m, -n)) {
	count++;
      }
    }
  }

  if (count == 8) return true;
  return false;
}

int main() {
  int number;
  cin >> number;
  for (int times = 0; times < number; times++) {
    int m, n;
    cin >> m >> n;

    if (isPrime(m, n)) cout << "P" << endl;
    else cout << "C" << endl;
  }

  return 0;
}