A tuple of three numbers ($a$, $b$, $c$) is called a pairwise coprime triple if $\gcd(a, b) = 1$, $\gcd(b, c) = 1$, and $\gcd(c, a) = 1$.

Let $C(n)$ be the number of pairwise coprime triples which satisfy $1 \le a, b, c \le n$.

For example, $C(3)$= #{(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 3), (1, 3, 1), (1, 3, 2), (2, 1, 1), (2, 1, 3), (2, 3, 1), (3, 1, 1), (3, 1, 2), (3, 2, 1)} = 13.

Given $N$, find $C(N)$.

Input

First line contains $T$ ($1 \le T \le 500$), the number of test cases.

Each line of the next $T$ lines contains a single integer $N$ ($1 \le N \le 100000$).

It is guaranteed that $\sum N \le 100000$ in each input file.

Output

For each number $N$, output a single line containing $C(N)$.

Example

Input

5
1
2
3
10
100

Output

1
4
13
280
282814

Information

There are 5 input files.

My C++ solution runs in 3.04 sec. (in the worst case)