Description:


给定一个正整数 \(N(N\le 2^31-1)\)
\(ans1=\sum_{i=1}^n \varphi (i),ans2 = \sum_{i=1}^n \mu (i)\)
多组询问。

Input:


一共 \(T+1\)
第1行为数据组数 \(T(T\le 10)\)
第2~ \(T+1\) 行每行一个非负整数 \(N\) ,代表一组询问

Output:


一共T行,每行两个用空格分隔的数 \(ans1,ans2\)

Sample Input:


Sample Output:


题解:


一道杜教筛的模板题,需要卡一下常数。
\(\mu\) 函数为例,设 \(M\)\(\mu\) 前缀和。

我们线性筛出前 \(n^{\frac {2}{3}}\) 项(这个貌似是复杂度的一个平衡点),然后记忆化一下就可以了。
需要用Hash卡一下常数。