505048 - 杜教筛

【题目描述】杜教筛(DuSieve)

给定一个正整数,求∑(i=1)^n▒〖φ(i)〗和∑(i=1)^n▒〖μ(i)〗的值。

Input

第一行为一个整数T,表示测试数据组数。 接下来T行,每行一个整数n,表示一组询问。

Output

对于每组询问,输出一行两个整数,分别代表要求的两个值。

Examples

Input

6
1
2
8
13
30
2333

Output

1 1
2 0
22 -2
58 -3
278 -3
1655470 2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题