Числа Гинкго
Мы определим числа Гинкго и операцию умножения для них.
Число Гинкго — это пара <m, n>, где m и n — целые числа. Например, <1, 1>, <-2, 1> и <-3, -1> — это числа Гинкго.
Умножение чисел Гинкго определяется следующим образом: <m, n>·<x, y> = <mx-ny, my+nx>.
Например, <1, 1>·<-2, 1> = <-3, -1>.
Число Гинкго <m, n> называется делителем числа Гинкго <p, q>, если существует число Гинкго <x, y> такое, что <m, n>·<x, y> = <p, q>.
Для любого числа Гинкго <m, n>, числа Гинкго <1, 0>, <0, 1>, <-1, 0>, <0, -1>, <m, n>, <-n, m>, <-m, -n> и <n, -m> являются делителями <m, n>. Если m^2+n^2 > 1, то эти числа Гинкго различны. Иными словами, любое число Гинкго, для которого m^2 + n^2 > 1, имеет как минимум восемь делителей.
Число Гинкго <m, n> называется простым, если m^2+n^2 > 1 и у него ровно восемь делителей. Ваша задача — определить, является ли данное число Гинкго простым.
Следующие два факта могут быть полезны для проверки, является ли число Гинкго делителем другого числа Гинкго.
Предположим, что m^2 + n^2 > 0. Тогда <m, n> является делителем <p, q>, если и только если целое число m^2 + n^2 является общим делителем mp + nq и mq - np.
Если <m, n>·<x, y> = <p, q>, то (m^2 + n^2)(x^2 + y^2) = p^2 + q^2.
Входные данные
Первая строка ввода содержит одно целое число, которое обозначает количество наборов данных. Остальная часть ввода — это последовательность наборов данных. Каждый набор данных — это строка, содержащая два целых числа m и n, разделенных пробелом. Они обозначают число Гинкго <m, n>. Можно предположить, что 1 < m^2 + n^2 < 20000.
Выходные данные
Для каждого набора данных выведите символ 'P' в строке, если число Гинкго является простым. В противном случае выведите символ 'C' в строке.