Ginkgo Nömrələri
Biz Ginkgo ədədlərini və onların vurma əməliyyatını öyrənəcəyik.
Ginkgo ədədi <m, n> cütlüyü ilə ifadə olunur, burada m və n tam ədədlərdir. Məsələn, <1, 1>, <-2, 1> və <-3, -1> Ginkgo ədədləridir.
Ginkgo ədədlərinin vurulması belə təyin edilir: <m, n>·<x, y> = <mx-ny, my+nx>.
Məsələn, <1, 1>·<-2, 1> = <-3, -1>.
Ginkgo ədədi <m, n> Ginkgo ədədi <p, q>-in böləni adlanır, əgər <m, n>·<x, y> = <p, q> bərabərliyini ödəyən bir Ginkgo ədədi <x, y> varsa.
Hər hansı bir Ginkgo ədədi <m, n> üçün, Ginkgo ədədləri <1, 0>, <0, 1>, <-1, 0>, <0, -1>, <m, n>, <-n, m>, <-m, -n> və <n, -m> <m, n>-in bölənləridir. Əgər m^2+n^2 > 1 olarsa, bu Ginkgo ədədləri fərqlidir. Başqa sözlə, m^2 + n^2 > 1 olan hər hansı bir Ginkgo ədədi ən azı səkkiz bölənə malikdir.
Ginkgo ədədi <m, n> sadə adlanır, əgər m^2+n^2 > 1 və onun dəqiq səkkiz böləni varsa. Sizin vəzifəniz verilmiş Ginkgo ədədinin sadə olub-olmadığını yoxlamaqdır.
Aşağıdakı iki fakt Ginkgo ədədinin başqa bir Ginkgo ədədinin böləni olub-olmadığını yoxlamaq üçün faydalı ola bilər.
Tutaq ki, m^2 + n^2 > 0. Onda, <m, n> <p, q>-in böləni olur, əgər və yalnız əgər tam ədəd m^2 + n^2 mp + nq və mq - np-nin ümumi böləni olarsa.
Əgər <m, n>·<x, y> = <p, q> olarsa, onda (m^2 + n^2)(x^2 + y^2) = p^2 + q^2.
Giriş verilənləri
Girişin ilk sətri datasetlərin sayını göstərən tək tam ədəddir. Girişin qalan hissəsi datasetlər ardıcıllığıdır. Hər dataset bir sətirdə boşluqla ayrılmış iki tam ədəd m və n ehtiva edir. Onlar Ginkgo ədədini <m, n> təyin edir. Siz 1 < m^2 + n^2 < 20000 olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Hər dataset üçün, əgər Ginkgo ədədi sadədirsə, bir sətirdə 'P' simvolunu çıxarın. Əks halda, bir sətirdə 'C' simvolunu çıxarın.