T620314 BZOJ3739 DZY loves math VIII

在XYZ的dzy loves math6问世后，dzy一直觉得这道题答案太大，一点都不优美，于是他随手在外面套上一个$\mu$。同时，他又觉得输入两个数实在太麻烦，于是题目变成了$\sum_{i=1}^n\sum_{j=1}^i\mu(lcm(i,j)^{gcd(i,j)})$，你能解决这个问题吗？

第一行一个整数T表示询问组数，接下来T行每行一个整数n。

对于每一个询问输出一行表示答案

$T