Задачи
Функция Мертенса
Функция Мертенса
Функция Мёбиуса μ(n) – мультипликативная функция, названная так в честь известного математика девятнадцатого столетия Августа Мёбиуса, знаменитого также своей лентой. Определяется функция следующим рекуррентным соотношением:
Функция Мёбиуса связана с функцией Мертенса соотношением:
Вычислить значение функции Мертенса по заданному числу n.
Входные данные
В первой строке задано количество тестов t (1 ≤ t ≤ 10^5
). Каждый тест состоит из единственного числа n (1 ≤ n ≤ 10^7
).
Выходные данные
Для каждого теста выведите в отдельной строке значение функции Мертенса.
Пример
Входные данные #1
4 2 1 4 7
Выходные данные #1
0 1 -1 -2