Функція Мертенса

Функція Мебіуса μ(n) – мультиплікативна функція, названа так на честь відомого математика дев'ятнадцятого століття Августа Мебіуса, відомого також своєю стрічкою. Визначається функція наступним рекурентним співвідношенням:

Функція Мебіуса пов'язана з функцією Мертенса співвіношенням:

Потрібно знайти значення функції Мертенса за заданиом числом n.

Вхідні дані

У першому рядку вхідного файла задано кількість тестів t (1 ≤ t ≤ 100000). Кожен тест складається з єдиного числа n (1 ≤ n ≤ 10^7).

Вихідні дані

Для кожного тесту у окремому рядке виведіть єдине число, яке є відповіддю до задачі.

Приклади