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.

Input

The first line contains the number of tests t (1 ≤ t ≤ 105). Each test consists of a single number n (1 ≤ n ≤ 107).

Output

For each test case print on a separate line the value of Mertens function.