#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int q;
  cin >> q;
  REP(k, q) {
    int m, n;
    cin >> m >> n;
    int cnt = 0;
    auto f = [](int x, int y) { return x * x + y * y; };
    REP(i, 2 * 200 + 1) REP(j, 2 * 200 + 1) {
      int x = i - 200;
      int y = j - 200;
      if (f(x, y) <= 0 || 20000 < f(x, y)) continue;
      if (abs(x * m + y * n) % f(x, y) == 0 && abs(x * n - y * m) % f(x, y) == 0) cnt++;
    }
    cout << ((cnt == 8) ? 'P' : 'C') << endl;
  }
}

