Para dos enteros ~A~ y ~B~ se define el ~mcm(A, B)~ como su mínimo común múltiplo, formalmente sea ~A = \displaystyle\prod_{p} p^{\alpha_p}~ y ~B = \displaystyle\prod_{p} p^{\beta_p}~, con ~p~ primo:

$$\displaystyle mcm(A,B)=\displaystyle\prod_{p} p^{\max(\alpha_p, \beta_p)}$$

Sea ~f(x)~ la cantidad de pares de números naturales ~(a,b)~ cuyo mínimo común múltiplo es igual a ~x~, formalmente:

$$\displaystyle ~f(x)=\big|\big\{(a,b):a\in\mathbb{N},b\in\mathbb{N} \land x=mcm(a,b)\big\}\big|~$$

Para un ~N~ dado calcule ~S_f(N)~:

$$\displaystyle ~S_f(N)=\sum_{i=1}^Nf(i)~$$

Entrada

La primera línea de la entrada contiene un entero ~T~ ~-~ la cantidad de casos de prueba.

Le siguen ~T~ líneas, cada una contiene un entero ~N~.

Salida

La salida debe contener ~T~ líneas ~-~ el valor de ~S_f(N)~ correspondiente a cada caso de prueba.

Restricciones

• ~1 \le T \le 100~
• ~1 \le N \le 10^{11}~
• ~\sum N \le 10^{11}~

Subtareas

Subtarea	Restricciones Adicionales	Puntos	Dependencias
~1~	~\sum N \leq 10^2~	~6~	~-~
~2~	~\sum N \leq 10^3~	~9~	~1~
~3~	~\sum N \leq 10^4~	~15~	~1-2~
~4~	~\sum N \leq 10^6~	~22~	~1-3~
~5~	~\sum N \leq 10^7~	~14~	~1-4~
~6~	~\sum N \leq 10^9~	~21~	~1-5~
~7~	~-~	~13~	~1-6~

Ejemplos

Entrada 1

4
1
6
19
100

Salida 1

1
24
117
1194

Para ~N=6~:

• ~i=1~: ~\big|\big\{(1,1)\big\}\big|=1~.
• ~i=2~: ~\big|\big\{(1,2),(2,1),(2,2)\big\}\big|=3~.
• ~i=3~: ~\big|\big\{(1,3),(3,1),(3,3)\big\}\big|=3~.
• ~i=4~: ~\big|\big\{(1,4),(2,4),(4,1),(4,2),(4,4)\big\}\big|=5~.
• ~i=5~: ~\big|\big\{(1,5),(5,1),(5,5)\big\}\big|=3~.
• ~i=6~: ~\big|\big\{(1,6),(2,3),(2,6),(3,2),(3,6),(6,1),(6,2),(6, 3),(6,6)\big\}\big|=9~.

Por lo tanto, ~S_f(6)=1+3+3+5+3+9=24~.

Entrada 2

3
314
3141592
31415926535

Salida 2

5254
267578356
6446663290425