/*
 * 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 <iostream>
using std::cin;
using std::cout;
using std::endl;

template<typename Int>
inline Int
sq(Int x)
{
	return x * 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 = sq(m) + sq(n);
	switch (N) {
	case 0:
		return G_ZERO;
	case 1:
		return G_UNIT;
	}
	for (Int k = 2; sq(sq(k)) <= N; k ++) {
		if (n % k == 0 && m % k == 0)
			return G_COMPOSITE;
	}
	for (Int h = 1; sq(sq(h)) <= N; h ++) {
		for (Int k = 1; sq(sq(h) + sq(k)) <= N; k ++) {
			const Int	K = sq(h) + sq(k);
			if ((m * h + n * k) % K == 0 && (m * k - n * h) % K == 0)
				return G_COMPOSITE;
		}
	}
	return G_PRIME;
}

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;
}