Mertens function#3239
Sign in

Mertens function

1 second
128 megabytes
Very easy

The Möbius function is a multiplicative arithmetic function named after the 19th-century German mathematician August Ferdinand Möbius, who is also famous for the discovery of the Möbius strip.

The Möbius function is defined as follows:

\mu(n)= \begin{cases} 1, & n=1,\\ 0, & \text{if } n \text{ is divisible by the square of a prime number},\\ (-1)^k, & \text{if } n \text{ can be represented as a product of } k \text{ distinct prime numbers}. \end{cases}

The Möbius function is related to the Mertens function by the following relation:

M(n)=\sum_{k=1}^{n}\mu(k).

Compute the value of the Mertens function for each given value of .

Input

The first line contains the number of test cases (1\le t\le 10^5).

Each of the following lines contains an integer (1\le n\le 10^7).

Output

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

Examples

Example 1

Loading
Loading