T129723 Hibiscus Garden

**如果你进行了一些常数优化并尝试后还TLE，那么完全可能是你的算法假了而非你的常数有问题。** 众所周知，Hibiscus Garden 的中文是芙蓉园。

小 U 是一个非常友善的初中生，他闲来无事喜欢去芙蓉园逛逛。这天他在芙蓉园里逛的时候想着想着想出了一个数学题： $$\sum_{i=1}^n\frac{i\times\mu(\gcd(i,n))\times n}{\operatorname{lcm}(i,n)}$$ 其中 $\mu$ 为莫比乌斯函数。 小 U 拿着这个式子不会算，因此去询问小 K。小 K 看了不到 $1.3s$ 以内就算出了答案。小 U 觉得很神奇，因此他来请教请教你。 小 U 现在有一个 $n$，他想请你计算出这个式子的值。**多组数据。**

**本题包含多组数据。** 输入第一行一个数 $T$。 接下来 $T$ 行，每行一个正整数 $n$，含义如题所示。

输出共 $T$ 行，每行一个正整数表示结果。

样例一的解释： 由输入得 $n=3$。因为 $\text{原式}=1\times \mu(1)+1\times \mu(1)+3\times \mu(3)=-1$，所以结果为 $-1$。 --- 对于 $10\%$ 的数据，满足 $1\leq T\leq 20,n\leq 10^3$。 对于 $40\%$ 的数据，满足 $1\leq T\leq 500,n\leq 10^6$。 对于 $75\%$ 的数据，满足 $1\leq T\leq 5000,n\leq 10^{15}$。 对于 $85\%$ 的数据，满足 $1\leq T\leq 5000,n\leq 1\times10^{18}$。 对于 $100\%$ 的数据，满足 $1\leq T\leq 5000,n\leq3\times10^{18}$，**时间限制**为 $1.3s$。 除特殊说明外时限为 $1s$。同一部分分内的数据也有梯度。 **如果有需要，请自行打开 O2 优化开关。** --- 注：不知道莫比乌斯函数的可以看 [这里](https://oi-wiki.org/math/mobius/#_11) 中莫比乌斯函数的定义。 本题允许使用 [__int128](https://www.cnblogs.com/ECJTUACM-873284962/p/9198885.html)，如果对此不了解请点击链接。