Distinct rational numbers

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

Medium5MathNumber theoryCombinatoricsPrefix sumNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

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.