The Mobius function μ(n) – a multiplicative function, so named after the famous nineteenth-century mathematician August Mobius, the well-known as his band. Function is defined in the following recurrence relation:
The Mobius function is associated with the function of Mertens' equation:
Find the value of Mertens function for a given number n.
The first line contains the number of tests t (1 ≤ t ≤ 10^5
). Each test consists of a single number n (1 ≤ n ≤ 10^7
).
For each test case print on a separate line the value of Mertens function.