Warning

Here is a harder version of Amazing Factor Sequence .

To make things clear, you'll need a O(n^0.5) method to solve this problem. You'll need to be careful with container of C-like language, and/or you'll need to find some little optimizations with slower language.

The factor sequence

We define our factor sequence with:

a[0] = a[1] = 0, and

for n > 1, a[n] = a[n - 1] + sum({x | x < n and n % x = 0}).

Input

First line of input contains an integer T, the number of test cases.

Each of the next T lines contains a single integer n.

Output

For each test case, print a[n] on a single line.

Example

Input:
3
3
4
5

Output:
2
5
6

Constraints

0 < T < 101
0 < n < 12148001999

Numbers n are uniform-randomly chosen. Nmax was carefully chosen ;-)
Time limit is ×2.5 my python one (2.56s). (Edited 2017-02-11, after compiler changes)