A natural number $d$ is a unitary divisor of $n$ if $d$ is a divisor of $n$ and if $d$ and $\frac{n}{d}$ are coprime.

Let $\sigma^{*}(n)$ be the sum of the unitary divisors of $n$. For example, $\sigma^{*}(1) = 1$, $\sigma^{*}(2) = 3$ and $\sigma^{*}(6) = 12$.

Let $S(n) = \sum_{i=1}^n \sigma^{*}(i).$

Given $n$, find $S(n) \bmod 2^{64}$.

Input

There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 50000$), indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 5 \times 10^{13}$).

Output

For each test case, output a single line containing $S(n) \bmod 2^{64}$.

Example

Input:

7
1
2
3
4
5
100
100000

Output:

1
4
8
13
19
6889
6842185909

Information

There are 8 Input files.

• Input #1: $1 \le n \le 50000$, TL=1s
• Input #2: $1 \le T \le 1000, \ 1 \le n \le 5 \times 10^7$, TL=5s
• Input #3: $1 \le T \le 300, \ 1 \le n \le 5 \times 10^8$, TL=5s
• Input #4: $1 \le T \le 80, \ 1 \le n \le 5 \times 10^9$, TL=5s
• Input #5: $1 \le T \le 30, \ 1 \le n \le 5 \times 10^{10}$, TL=10s
• Input #6: $1 \le T \le 10, \ 1 \le n \le 5 \times 10^{11}$, TL=10s
• Input #7: $1 \le T \le 3, \ 1 \le n \le 5 \times 10^{12}$, TL=10s
• Input #8: $T=1, \ 1 \le n \le 5 \times 10^{13}$, TL=10s

My unoptimized C++ solution runs in 8.9 sec (total time). And with some constant optimization, now my C++ solution runs in 1.03 sec (total time).