【模板】杜教筛(Sum)

题目描述

给定一个正整数$N(N\le2^{31}-1)$ 求 $$ans_1=\sum_{i=1}^n\varphi(i)$$ $$ans_2=\sum_{i=1}^n \mu(i)$$

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

6
1
2
8
13
30
2333

输出样例 #1

1 1
2 0
22 -2
58 -3
278 -3
1655470 2