eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

prb3239-1

Функция Мёбиуса связана с функцией Мертенса соотношением:

prb3239-2

Вычислить значение функции Мертенса по заданному числу n.

Входные данные

В первой строке задано количество тестов t (1t10^5). Каждый тест состоит из единственного числа n (1n10^7).

Выходные данные

Для каждого теста выведите в отдельной строке значение функции Мертенса.

Пример

Входные данные #1
4
2
1
4
7
Выходные данные #1
0
1
-1
-2
Автор Евгений Служаев