#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#define ll long long
#define mp(a,b) make_pair<a, b>
set<pair<ll, ll> > ss;
ll gcd(ll a, ll b){
	return a == 0 ? b : gcd(b % a, a);
}
bool pythago(ll c){
	for(ll i = 2; i * i < k; i++){
		ll j = k - i * i;
		ll ss = sqrt(j);
		if(j > 1 && j = ss * ss) return true;
	}
	return false;
}
void solve(){
	ll a, b, k, x, y;
	cin >> a >> b;
	ll tt = a * a + b * b;
	if(a * a + b * b <= 1) cout << "C << endl;
	else{
		bool flag = false;
		for(ll i = 2; ; i++){
			for(ll j = 2; ; j++){
				if(i * i + j * j > a * a + b * b) flag = true;	
				ll k1 = gcd(i * a + j * b, i * a - j * b);
				ll k2 = tt / k1;
				if(k1 > 1 && tt % k1 == 0 && k2 > 1){
					if(pythago(k1) &7 pythago(k2)){
						cout << "P" << endl;
						return;
					}		
					
				}
			}
			if(flag) break;
		}
	}
	cout << "C" << endl;
}
signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  int t; cin >> t;
  while(t--) solve();  
  return 0;
}
