Migrated from Lutece 2492 Was yant gagis chs hymmnos mea

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

——霜月はるか - EXEC_LINCA/.

如果不想读这么长，可以直接跳到题面最后。

---

「所以，昨天到底是怎么回事啊？」

「我说能不能讨论点其他话题啊？」

显然，昨天的 Alice 确实不太对劲。她性格再怎么差也不至于像昨天那样一直缠着人不放。最终还是因为肚子都饿了，才结束这 100 胜 5 负的战局。

用其他的话来说，昨天的她有一点“疯狂(krazy)”。

「呐，Bob，你知道什么是最大公因数 (gcd) 吗？」

「如果我连这都不知道都可以被这座岛除名了」

看得出来，她是在回避这个问题。

「那好，你知道怎么求两个数的 gcd 吗？」

「我知道你很聪明，什么都知道。但问这个干嘛？」

「能好好回答我的问题吗？」

「行行行，我知道。不就是什么辗转相除啊，更相减损这些吗」

「很好，我今天会给你说一个另外的函数，叫做 $\mu$」

「第一，我不知道你怎么突然要跟我说这个。第二，这个读作 meow？你是在学猫叫吗？」

「你的耳朵长着是作摆设的吗？还是说昨天的惨败让你的脑子与耳朵之间的神经断开了？」

「好好好，大小姐您继续」

行吧，莫名其妙的事情也就习以为常了，更何况还是直接面对她呢。

「设 $x$ 为一个正整数，那么 $\mu(1)=1$，如果 $x$ 含有平方因子则 $\mu(x)=0$，否则 $\mu(x)=(-1)^k$，其中 $k$ 为本质不同的质因子个数。」

「嗯......」Bob 一听到这些就立刻走神了。

「看来你那脑子也是摆设，干脆丢掉算了」

「你能一脸平静地说出如此儒雅随和地话我也是挺佩服的」

「那么，你听懂了吗？」

「懂懂懂」Bob 可不想也不敢说不懂 「可是这有什么用呢？」

「我来给你出道题你就知道了」

求

$$\sum\limits_{i=1}^n\mu(\gcd(i,n))\gcd(i,n)$$

「题目懂了吗？」

「这......」Bob 一时无语。她的人生就只有做题出题还有儒雅随和吗？

「如何？」

「不如何，没头绪到理都不想理这个题」

「很好，看来你的脑子今晚就可以丢掉了」

「为什么啊？虽然我知道你很喜欢出些怪题，但这和你昨天的事有什么联系吗？」

「我・不・是・说・过・不・要・说・那・件・事・了・吗？」

......气氛有些尴尬。

「行吧，我再问你个问题。如果，我是说如果，我被选去担任这一次的圣女，你会怎么想？」

「哦，那很好啊，肯定是恭喜你啦。但是一想到是让你去当，那这座岛还真的就应该完了」

「......不是应该」Alice 说得非常小声。

「你说什么？」

「算了，没，没事。另外，我倒是希望你能够好好思考这个问题」

「你希望起我来了？」

「就当是个约定嘛，如果你做出来了，之后我不会再给你出题为难你了」

「这话不能当作没听到啊」

「总之，限定今晚，你必须得做出来才行」

「啊这，好吧好吧......」Bob 再一次感到无奈。

---

求

$$\sum\limits_{i=1}^n\mu(\gcd(i,n))\gcd(i,n)$$

其中 $\mu$ 表示莫比乌斯函数。

Input

第一行一个正整数 $T$，表示有 $T$ 组数据；

接下来每一行一个正整数 $n$。

Output

每一组数据一个整数表示结果。

Samples

2
6
666

1
0

Constraints

$1\le T \le 2\times 10^4,1\le n \le 10^{12}$

数据保证单个测试点 $n\ge 10^{10}$ 不超过 $3000$ 组。

Resources

2020 UESTC ICPC Training for Math and Geometry