#include<iostream>
using namespace std;
int main()
{
	int n;cin>>n;
	for(;n--;)
	{
		long a,b;cin>>a>>b;
		int cnt=0;
		for(long i=-500;i<=500;i++)for(long j=-500;j<=500;j++)
		{
			if(!i&&!j||i*i+j*j>a*a+b*b)continue;
			cnt+=(i*a+j*b)%(i*i+j*j)==0&&(i*b-j*a)%(i*i+j*j)==0;
		}
		cout<<(cnt==8?"P":"C")<<endl;
	}
}

