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

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

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

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

В первой строке задано количество тестов t (1 ≤ t ≤ 105). Каждый тест состоит из единственного числа n (1 ≤ n ≤ 107).

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

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