注意:

有 $T$ 组数据

每一组给出 $n$ ，要求得到：

注意范围

• $n\le10^7$
• $T\le 10^6$

时限：$3S$

空间： $1GB$

我的做法：

化简+整除分块时间复杂度为 $O(n+t\sqrt n\log n)$

过不了。

问题

求问大佬有更加快的算法或者还可以怎么优化吗？