Kvadrat qalıqlarının sayı

Qoy m hər hansı bir natural ədəd olsun. Əgər a ədədi {0, 1, ..., m-1} dəstinə aid olub və elə bir tam ədəd x varsa ki, x^2-a m-ə bölünürsə, o zaman a m modulu üzrə kvadratik qalıq adlanır. Sizə m verilir və sizdən m modulu üzrə kvadratik qalıqların sayını tapmaq tələb olunur.

Giriş verilənləri

Giriş faylının ilk sətirində T ≤ 100 natural ədədi, yəni fayldakı natural ədədlərin sayı verilir. Növbəti T sətirlərdə isə bu ədədlər verilir. Hər bir ədədin 10^12-dən çox olmadığı təmin edilir.

Çıxış verilənləri

Giriş faylındakı hər bir natural m ədədi üçün ayrıca sətirdə m modulu üzrə kvadratik qalıqların sayını çıxarın.

Nümunələr