SP20872 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) $ .

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.

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