T237759 Simple

小 B 认为，题面应该是简洁的。

有 $T$ 次询问，每次给定正整数 $n$，你需要计算出小于等于 $n$ 的正整数中，有多少数满足其欧拉函数值整除它本身。 也就是说，你需要计算 $\sum\limits_{i=1}^{n}[\varphi(i)|i]$ 的值。

第一行为一个正整数 $T$，表示数据组数。 接下来 $T$ 行，每行一个正整数 $n$，含义见题目描述。

共 $T$ 行，表示每次询问的答案。

**【样例 $1$ 解释】** 列出 $\varphi(i)$ 和 $i$ 的表格： |$i$|$\varphi(i)$|整除| | :-----------: | :-----------: | :-----------: | |$1$|$1$|是| |$2$|$1$|是| |$3$|$2$|否| |$4$|$2$|是| |$5$|$4$|否| |$6$|$2$|是| |$7$|$6$|否| |$8$|$4$|是| |$9$|$6$|否| |$10$|$4$|否| 故答案为 $5$。 **【数据规模与约定】** |测试点|$T$|$n$| | :----------: | :----------: | :----------: | |$1$|$\leqslant 10$|$\leqslant 10$| |$2$|$\leqslant 10$|$\leqslant 10^7$| |$3$|$\leqslant 10^6$|$\leqslant 10^7$| |$4$|$\leqslant 10$|$\leqslant 10^9$| |$5$|$\leqslant 10$|$\leqslant 10^{18}$| |$6$|$\leqslant 10^5$|$\leqslant 10^9$| |$7\sim8$|$\leqslant 10^5$|$\leqslant 10^{18}$| |$9\sim10$|$\leqslant 10^6$|$\leqslant 10^{18}$| 对于所有数据，满足 $1\leqslant T\leqslant 10^6,1\leqslant n\leqslant 10^{18}$。