// AOJ 1325: Ginkgo Numbers
// 2017.10.3 bal4u@uu

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int a[100], sz;

int cmp(int *a, int *b) { return *a - *b; }

int main()
{
	int t, i, m, n, mn, k;

	for (sz = 0, m = 0; m <= 12; m++) for (n = m; n <= 12; n++) {
		mn = m*m + n*n;
		if (mn > 1 && mn <= 150) a[sz++] = mn;
	}
	qsort(a, sz, sizeof(int), cmp);

	scanf("%d", &t);
	while (t-- > 0) {
		scanf("%d%d", &m, &n);
		mn = m*m + n*n;
		k = (int)sqrt(mn);
		for (i = 0; a[i] <= k; i++) if (mn % a[i] == 0) break;
		puts(a[i] > k ? "P" : "C");
	}
	return 0;
}