Distinct rational numbers

Time limit2sMemory limit512 MB

Summary

Count distinct values of a/b with 0 <= a <= b <= N, i.e. fractions in [0,1] with reduced denominator at most N.

Level: Medium5 of 10
Topics: Math, Number theory, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

You are given a positive integer $N$ . Count how many distinct values the fraction $\frac{a}{b}$ takes over all integers $a$ and $b$ with $0 \le a \le b \le N$ . A denominator cannot be $0$ , so $b$ is at least $1$ . Fractions with the same value are counted once. For example, $\frac{1}{2}$ and $\frac{2}{4}$ have the same value, so they count as one.

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 10000$ ). Each of the next $t$ lines contains one integer $N$ ( $2 \le N \le 10000$ ).

Output

For each test case, print the number of distinct rational numbers on its own line.

Examples3

Example 1
Input
```
4
6
15
57
9999
```
Expected output
```
13
73
1001
30393487
```
Example 2
Input
```
1
2
```
Expected output
```
3
```
Example 3
Input
```
1
3
```
Expected output
```
5
```