#include <stdio.h>

//FILE *in = freopen("input.txt", "r", stdin);
//FILE *out = freopen("output.txt", "w", stdout);

int p, q;

void process() {
	int cnt = 0;
	int x, y, z;
	for(int n = -150; n < 150; n++) {
		for(int m = -150; m < 150; m++) {
			x = m*p - n*q;
			y = m*q + n*p;
			z = m*m + n*n;
			if(z == 0) continue;
			if(x % z == 0 && y % z == 0) ++cnt;
		}
	}
	if(cnt > 8) {
		printf("C\n");
	}
	else {
		printf("P\n");
	}
}

void output() {
}

int main() {
	int N;
	scanf("%d", &N);
	for(int i = 0; i < N; i++) {
		scanf("%d%d", &p, &q);
		process();
		output();
	}
	return 0;
}