<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css" integrity="sha384-wITovz90syo1dJWVh32uuETPVEtGigN07tkttEqPv+uR2SE/mbQcG7ATL28aI9H0" crossorigin="anonymous">

Let $\sigma_0(n)$ be the number of positive divisors of $n$.

For example, $\sigma_0(1) = 1$, $\sigma_0(2) = 2$ and $\sigma_0(6) = 4$.

Let $$S_2(n) = \sum _{i=1}^n \sigma_0(i^2).$$

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

Input

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

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

Output

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

Example

Input

5
1
2
3
10
100

Output

1
4
7
48
1194

Explanation for Input

- $S_2(3) = \sigma_0(1^2) + \sigma_0(2^2) + \sigma_0(3^2) = 1 + 3 + 3 = 7$

Information

There are 6 Input files.

- Input #1: $1 \le N \le 10000$, TL = 1s.

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

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

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

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

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

My C++ solution runs in 5.3 sec. (total time)

Source Limit is 6 KB.