#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

typedef pair<int, int> PII;

int main ( void )
{
	int t;
	while ( cin >> t ) {
	while ( t-- ) {
		int m, n;
		cin >> m >> n;
		
		set<PII> divisor;
		
		/*divisor.insert( PII(  1,  0 ) );
		divisor.insert( PII(  0,  1 ) );
		divisor.insert( PII( -1,  0 ) );
		divisor.insert( PII(  0, -1 ) );
		divisor.insert( PII(  m,  n ) );
		divisor.insert( PII( -n,  m ) );
		divisor.insert( PII( -m, -n ) );
		divisor.insert( PII(  n, -m ) );*/

		int l = max( abs( m ), abs( n ) );
		for ( int i = 0; i <= l; ++i ) {
			for ( int j = 0; j <= l; ++j ) {
				for ( int d1 = -1; d1 < 2; d1 += 2) {
					for ( int d2 = -1; d2 < 2; d2 += 2 ) {
						int p = m, q = n, _m = i * d1, _n = j * d2,
							xd = _m * p + _n * q,
							yd = _n * p - _m * q,
							nm = _n * _n + _m * _m;
						if ( ( nm > 0 ) && ( xd % nm == 0 ) && ( yd % -nm == 0 ) ) {
							int x = xd / nm, y = yd / -nm;
							divisor.insert( PII( _m, _n ) );
							//divisor.insert( PII( xd / nm, yd / -nm ) );
						}
					}
				}
			}
		}

		cout << ( divisor.size() == 8 ? "P" : "C" ) << endl;
	}
	}
	return 0;
}