Пусть m некоторое натуральное число. Число a Є {0, 1, ..., m-1} называется квадратичным вычетом по модулю m, если существует такое целое число x, что x^2-a делится на m. Вам дано m и требуется найти количество квадратичных вычетов по модулю m.
В первой строке входного файла задано натуральное число T ≤ 100, количество натуральных чисел m в файле. В последующих T строках заданы сами эти числа. Гарантируется, что каждое из них не превосходит 10^12.
Для каждого натурального числа m из входного файла выведите в отдельной строке количество квадратичных вычетов по модулю m.