Нехай \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}.