문제 114
오일러 피와 뫼비우스 함수의 누적합
양의 정수 $n$에 대해 오일러 피 함수 $\varphi(n)$은 $1$ 이상 $n$ 이하의 정수 중 $n$과 서로소인 정수의 개수이다.
뫼비우스 함수 $\mu(n)$은 다음과 같이 정의한다.
- $\mu(1)=1$이다.
- $n$이 어떤 소수의 제곱으로 나누어떨어지면 $\mu(n)=0$이다.
- 그 외에 $n$이 서로 다른 $k$개 소수의 곱이면 $\mu(n)=(-1)^k$이다.
각 질의에서 주어지는 음이 아닌 정수 $N$에 대해 $\sum_{i=1}^N\varphi(i)$와 $\sum_{i=1}^N\mu(i)$를 구해 보자. $N=0$이면 두 합은 모두 $0$이다.
입력
첫 번째 줄에 질의의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 3)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 정수 $N$이 주어진다. $(0 \le N \le 10^{10})$
출력
질의가 주어진 순서대로 각 질의의 $\sum_{i=1}^{N}\varphi(i)$와 $\sum_{i=1}^{N}\mu(i)$를 공백으로 구분하여 한 줄에 출력한다. 첫 번째 합은 부호 있는 $64$비트 정수의 범위를 넘을 수 있다.
예제 입력 1
3 0 1 10
예제 출력 1
0 0 1 1 32 -1