서로 다른 유리수의 개수

시간 제한2초메모리 제한512 MB

요약

0 ≤ a ≤ b ≤ N인 모든 a/b가 갖는 서로 다른 값을 센다. 기약분모가 N 이하인 [0,1] 구간 분수의 개수와 같다.

난이도: 보통10점 중 5점
유형: 수학, 정수론, 조합론, 누적 합
정답자: 아직 제출이 없습니다

문제

양의 정수 $N$ 이 주어진다. $0 \le a \le b \le N$ 을 만족하는 정수 $a$ 와 $b$ 로 분수 $\frac{a}{b}$ 를 만들 때, 서로 다른 값이 몇 개인지 세어라. 분모는 $0$ 이 될 수 없으므로 $b$ 는 $1$ 이상이다. 값이 같은 분수는 한 번만 센다. 예를 들어 $\frac{1}{2}$ 와 $\frac{2}{4}$ 는 값이 같으므로 하나로 센다.

입력

첫 줄에 테스트 케이스의 개수 $t$ 가 주어진다 ( $1 \le t \le 10000$ ). 이어지는 $t$ 개의 줄에 정수 $N$ 이 한 줄에 하나씩 주어진다 ( $2 \le N \le 10000$ ).

출력

각 테스트 케이스마다 서로 다른 유리수의 개수를 한 줄에 하나씩 출력한다.

예제3

예제 1
입력
```
4
6
15
57
9999
```
예상 출력
```
13
73
1001
30393487
```
예제 2
입력
```
1
2
```
예상 출력
```
3
```
예제 3
입력
```
1
3
```
예상 출력
```
5
```