Числа Гінкго#5412
Ми визначимо числа Гінкго та операцію множення для них.
Число Гінкго — це пара <m, n>, де та є цілими числами. Наприклад, <1, 1>, <-2, 1> та <-3, -1> є числами Гінкго.
Множення чисел Гінкго визначається як <m, n> \cdot <x, y> = <mx-ny, my+nx>.
Наприклад, <1, 1> \cdot <-2, 1> = <-3, -1>.
Число Гінкго <m, n> називається дільником числа Гінкго <p, q>, якщо існує число Гінкго <x, y>, таке що <m, n> \cdot <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> \cdot <x, y> = <p, q>, тоді (m^2 + n^2)(x^2 + y^2) = p^2 + q^2.
Перший рядок вхідних даних містить одне ціле число, яке є кількістю наборів даних. Решта вхідних даних — це послідовність наборів даних. Кожен набір даних — це рядок, що містить два цілі числа та , розділені пробілом. Вони позначають число Гінкго <m, n>. Ви можете припустити, що 1 < m^2 + n^2 < 20000.
Для кожного набору даних виведіть символ 'P' в рядку, якщо число Гінкго є простим. Виведіть символ 'C' в рядку в іншому випадку.
Приклад 1