Let $s_1(n)$ be the sum of positive proper divisors of $n$.

For example, $s_1(1) = 0$, $s_1(2) = 1$ and $s_1(6) = 6$.

Let $$S(n) = \sum _{i=1}^n s_1(i).$$

Given $N$, find $S(N)$.

Input

First line contains $T$ ($1 \le T \le 10^5$), the number of test cases.

Each of the next $T$ lines contains a single integer $N$. ($1 \le N < 2^{63}$)

Output

For each number $N$, output a single line containing $S(N)$.

Example

Input

6
1
2
3
10
100
1000000000000000000

Output

0
1
2
32
3249
322467033424113218863487627735401433

Information

There are 6 Input files.

- Input #1: $1 \le N \le 10^5$, TL = 2s.

- Input #2: $1 \le T \le 60,\ 1 \le N \le 10^{15}$, TL = 10s.

- Input #3: $1 \le T \le 25,\ 1 \le N \le 10^{16}$, TL = 10s.

- Input #4: $1 \le T \le 10,\ 1 \le N \le 10^{17}$, TL = 10s.

- Input #5: $1 \le T \le 5,\ 1 \le N \le 10^{18}$, TL = 10s.

- Input #6: $1 \le T \le 2,\ 1 \le N < 2^{63}$, TL = 10s.

My C++ solution runs in about 0.85 seconds for each Input #2 - #6.

Note

• Probably, $O(\sqrt{n})$ solutions will not pass.
• Intended solutions have a running time of about $O(n^{1/3} \log n)$.
• Time limits are somewhat strict.
• The answer can be $\ge 2^{64}$.
• DIVCNT1 is a little easier than this.