#PCOPTRIP. Counting Pairwise Coprime Triples
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)