Bhelu is the classmate of Bablu who made the Amazing Prime Sequence.

He felt jealous of his classmate and decides to make his own sequence. Since he was not very imaginative, he came up with almost the same definition just making a difference in f(n):

• a[0] = a[1] = 0.
• For n > 1, a[n] = a[n - 1] + f(n), where f(n) is the sum of positive integers in the following set S.
• S = {x | x < n and n % x = 0}.

Now, Bablu asked him to make a code to find f(n) as he already had the code of his sequence. So, Bhelu asks for your help since he doesn't know programming. Your task is very simple, just find a[n] for a given value of n (< 10^6).

Input

Your code will be checked for multiple test cases.

First Line of Input contains T (<= 100), the number of test cases.

Next T lines contain a single positive integer N. (1 < N < 10^6).

Output

Single line containing a[n] i.e. n-th number of the sequence for each test case.

Example

Input:
3
3
4
5

Output:
2
5
6

Explanation

f(2) = 1 {1}
f(3) = 1 {1}
f(4) = 3 {1, 2}
f(5) = 1 {1}