PCOPTRIP - Counting Pairwise Coprime Triples


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)


hide comments
universe_25: 2021-07-17 15:01:33

Very interesting problem, learn sth. new :)


Added by:Min_25
Date:2014-09-02
Time limit:8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64