Кількість квадратичних лишків#641
Нехай — деяке натуральне число. Число a \in \{0, 1, \ldots, m-1\} називається квадратичним лишком за модулем , якщо існує таке ціле число , що x^2 - a ділиться на . Вам задано і потрібно знайти кількість квадратичних лишків за модулем .
У першому рядку вхідного файлу задано натуральне число (1 \leq T \leq 100), кількість тестових випадків. У наступних рядках задано число . Гарантується, що кожне не перевищує 10^{12}.
Для кожного з вхідних даних виведіть у окремому рядку кількість квадратичних лишків за модулем .
Приклад 1