Кількість квадратичних лишків

Нехай m деяке натуральне число. Число a Є {0, 1, ..., m-1} називається квадратичним лишком за модулем m, якщо існує таке ціле число x, що x^2-a ділиться на m. Вам задано m і потрібно знайти кількість квадратичних лишків за модулем m.

Вхідні дані

У першому рядку вхідного файлу задано натуральне число T ≤ 100, кількість натуральних чисел m в файлі. У наступних T рядках задано самі ці числа. Гарантується, що кожне з них не перевищує 10^12.

Вихідні дані

Для кожного натурального числа m з вхідного файлу виведіть у окремому рядку кількість квадратичних лишків за модулем m.

Приклади