/*
 * Copyright (C) 2012, 2016, 2019  Hiroyasu Kamo
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * ACM-ICPC 2012 Asia Regional Contest, Tokyo
 *  Problem A  Ginkgo Numbers
 *
 *	Author: Hiroyasu Kamo <wd@ics.nara-wu.ac.jp>
 */

#include <limits>
#include <utility>
#include <iostream>
using std::numeric_limits;
using std::pair;
using std::make_pair;
using std::cin;
using std::cout;
using std::endl;

template<typename Int>
inline const pair<Int, Int>
isqrt(Int x)
{
	Int	y = 0;
	for (Int h = static_cast<Int>(1) << ((numeric_limits<Int>::digits - 1) / 2); h > 0; h /= 2) {
		const Int	a = (h + y * 2) * h;
		if (x >= a) {
			x -= a;
			y += h;
		}
	}
	return make_pair(y, x);
}

template<typename Int>
inline Int
floor_sqrt(Int x)
{
	return isqrt(x).first;
}

template<typename Int>
class basic_ginkgo {
private:
	Int	real, imag;
public:
	enum {G_ZERO, G_UNIT, G_PRIME, G_COMPOSITE};
	basic_ginkgo(Int m, Int n) : real(m), imag(n) {}
	int	classify() const;
};

template<typename Int>
int
basic_ginkgo<Int>::classify() const
{
	const Int	m = real;
	const Int	n = imag;
	const Int	N = m * m + n * n;
	const Int	s = floor_sqrt(N);
	Int	counter = 0;
	for (Int h = -s; h <= s; h ++) {
		const Int	s1 = floor_sqrt(N - h * h);
		for (Int k = -s1; k <= s1; k ++) {
			const Int	K = h * h + k * k;
			if (K > 0 && (m * h + n * k) % K == 0 && (m * k - n * h) % K == 0) {
				counter ++;
			}
		}
	}
	switch (counter) {
	case 0:
		return G_ZERO;
	case 4:
		return G_UNIT;
	case 8:
		return G_PRIME;
	}
	return G_COMPOSITE;
}

using ginkgo = basic_ginkgo<int>;

int
main()
{
	static const char	*names[] = {"Z", "U", "P", "C"};
	int	num;
	cin >> num;
	for (int i = 0; i < num; i ++) {
		int	m, n;
		cin >> m >> n;
		const ginkgo	x(m, n);
		cout << names[x.classify()] << endl;
	}
	return 0;
}