#include <iostream>
#include <cmath>
using namespace std;

int main() {
  int T;
  cin >> T;
  for (int t=0; t<T; t++) {
    int m, n;
    cin >> m >> n;
    int count = 0;
    for (int p=-200; p<200; p++) {
      for (int q=-200; q<200; q++) {
	if (p == 0 && q == 0) continue;
	int c = p*p+q*q;
	if ((p*m+q*n + c*20000)%c == 0 && (p*n-q*m + c*20000)%c == 0) count++;
      }
    }
    cout << (count == 8 ? 'P' : 'C') << endl;
  }
}