## 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

512310100


#### Output

1413280282814

### Information

There are 5 input files.

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

 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