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