In this problem, you will be given q queries (1 ≤ q ≤ 1 000 000). Each query will contain a single integer n (1 ≤ n ≤ 1 000 000).

For each query you have to output the following:

Input

First line will contain the number of queries q. Next q lines will contain a single integer n.

Output

Output the answer for each query in a new line.

Example

Input:
4
4
6
7
9
Output:
24
63
70
135

Explanation:

For second query (n=6):

1*gcd(1,6)+2*gcd(2,6)+3*gcd(3,6)+4*gcd(4,6)+5*gcd(5,6)+6*gcd(6,6)

1*1+2*2+3*3+4*2+5*1+6*6

1+4+9+8+5+36=63

EDIT: Reducing the time limit from 2s to 1s. Thanks to merlin__ for pointing that some "not fully optimized" codes are also getting submitted.