#P9594. Sum

    ID: 6211 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2200提高+/省选-杜教筛狄利克雷卷积整除分块线性筛记忆化搜索欧拉函数莫比乌斯函数

Sum

题目描述

给定一个正整数,求

ans1=∑i=1nφ(i)ans_1=\sum_{i=1}^n\varphi(i) ans2=∑i=1nμ(i)ans_2=\sum_{i=1}^n \mu(i)

输入格式

本题单测试点内有多组数据。

输入的第一行为一个整数,表示数据组数 TT。

接下来 TT 行,每行一个整数 nn,表示一组询问。

输出格式

对于每组询问,输出一行两个整数,分别代表 ans1ans_1 和 ans2ans_2。

样例

6
1
2
8
13
30
2333
1 1
2 0
22 -2
58 -3
278 -3
1655470 2

数据规模与约定

对于全部的测试点,保证 1≤T≤101 \leq T \leq 10,1≤n<2311 \leq n \lt 2^{31}。