/*
 * 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 <cstdlib>
#include <limits>
#include <utility>
#include <iostream>
using std::abs;
using std::numeric_limits;
using std::pair;
using std::make_pair;
using std::cin;
using std::cout;
using std::endl;

template<typename Int>
inline bool
isprime(Int x)
{
	if (x < 2)
		return 0;
	if (x % 2 == 0)
		return x == 2;
	if (x % 3 == 0)
		return x == 3;
	for (Int i = 5, d = 4; i * i <= x; d = 6 - d, i += d) {
		if (x % i == 0)
			return 0;
	}
	return 1;
}

template<typename Int>
inline bool
isprime3(Int x)
{
	x = abs(x);
	return x % 4 == 3 && isprime(x);
}

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;
	switch (N) {
	case 0:
		return G_ZERO;
	case 1:
		return G_UNIT;
	}
	return ((m == 0 && isprime3(n)) || (n == 0 && isprime3(m)) || isprime(N)) ? G_PRIME : 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;
}