Функція Мебіуса μ(n) – мультиплікативна функція, названа так на честь відомого математика дев'ятнадцятого століття Августа Мебіуса, відомого також своєю стрічкою. Визначається функція наступним рекурентним співвідношенням:
Функція Мебіуса пов'язана з функцією Мертенса співвіношенням:
Потрібно знайти значення функції Мертенса за заданиом числом n.
У першому рядку вхідного файла задано кількість тестів t (1 ≤ t ≤ 100000). Кожен тест складається з єдиного числа n (1 ≤ n ≤ 10^7).
Для кожного тесту у окремому рядке виведіть єдине число, яке є відповіддю до задачі.