B. Difference Engine
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$. Count the number of pairs of integers $$$(a, b)$$$ with $$$1 \le a \lt b \le n$$$ such that $$$(b - a)$$$ divides $$$a \cdot b$$$.

A non-zero integer $$$x$$$ divides an integer $$$y$$$ if there exists an integer $$$z$$$ such that $$$y = x \cdot z$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^6$$$) — the number of test cases.

The first and only line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^6$$$).

Output

For each test case, output a single integer — the number of pairs $$$(a, b)$$$ that satisfy the condition.

Example
Input
3
2
5
10
Output
1
5
19
Note

In the first test case, $$$n = 2$$$, and the only pair is $$$(1, 2)$$$: here $$$b - a = 1$$$ divides $$$a \cdot b = 2$$$, so the answer is $$$1$$$.

In the second test case, $$$n = 5$$$, the pairs that satisfy the condition are:

  • $$$(1, 2)$$$, since $$$1$$$ divides $$$2$$$;
  • $$$(2, 3)$$$, since $$$1$$$ divides $$$6$$$;
  • $$$(2, 4)$$$, since $$$2$$$ divides $$$8$$$;
  • $$$(3, 4)$$$, since $$$1$$$ divides $$$12$$$;
  • $$$(4, 5)$$$, since $$$1$$$ divides $$$20$$$.
For example, the pair $$$(2, 5)$$$ does not count, because $$$b - a = 3$$$ does not divide $$$a \cdot b = 10$$$. In total there are $$$5$$$ valid pairs.