Функція Мебіуса \textbf{μ(n}) -- мультиплікативна функція, названа так на честь відомого математика дев'ятнадцятого століття Августа Мебіуса, відомого також своєю стрічкою. Визначається функція наступним рекурентним співвідношенням: \includegraphics{https://static.e-olymp.com/content/51/5116064aa55a445611c7cb1e81b1d260b1a37c60.jpg} Функція Мебіуса пов'язана з функцією Мертенса співвіношенням: \includegraphics{https://static.e-olymp.com/content/7b/7b186d7b22e6974e81db87779ff8e53bf477d589.jpg} Потрібно знайти значення функції Мертенса за заданиом числом \textbf{n}. \InputFile У першому рядку вхідного файла задано кількість тестів \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{100000}). Кожен тест складається з єдиного числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^7}). \OutputFile Для кожного тесту у окремому рядке виведіть єдине число, яке є відповіддю до задачі.