A C-3IC se le ha ocurrido una nueva hipótesis, él cree que para todo entero positivo $n$, y todo par de enteros $(i,j)$, tal que $1\le i\le j\le n$ se cumple que $gcd(i,n)\cdot gcd(j,n)=gcd(i\cdot j,n)$.

C-3IC corrió hacia su PC para probar si su hipótesis era verdadera probando muchos casos, rápidamente notó que para un entero $n$ su hipótesis era válida solo en algunos pares $(i,j)$, decepcionado por no descubrir un nuevo teorema, quiere analizar las propiedades de los pares de números que cumplen su hipótesis, para lo cual le pide que resuelva la siguiente tarea:

Dado un entero positivo $n$, cuente el número de pares de enteros $(i,j)$ tales que $1\le i\le j\le n$ y $gcd(i,n)\cdot gcd(j,n)=gcd(i\cdot j,n)$.

Habrá $T(1\le T\le {10}^6)$ casos de prueba, en cada uno se le dará un entero $n(1\le n\le 4\cdot {10}^6)$.

Nota: $gcd(a,b)$ significa el máximo común divisor entre $a$ y $b$.

Subtareas:

• Subtarea 1: $1\le T\le 40$, $1\le n\le 40$. ( 5 puntos )

• Subtarea 2: $1\le T\le 100$, $1\le n\le {10}^5$, se garantiza que el divisor más pequeño de $n$ es mayor que $100$. (19 puntos)

• Subtarea 3: $1\le T\le {10}^4$, $1\le n\le {10}^5$, se garantiza que existe un primo $p$, tal que $p^k=n$ para un entero positivo $k$. (22 puntos)

• Subtarea 4: $1\le T\le {10}^5$, $1\le n\le {10}^5$. (25 puntos)

• Subtarea 5: $1\le T\le {10}^6$, $1\le n\le 4\ast {10}^6$. (29 puntos)

Formato de Entrada:

La primera línea contendrá la cantidad de casos $T$ a procesar.

A partir de ahí, seguirán $T$ líneas, cada una con un entero $n$.

Formato de Salida:

Debe imprimir $T$ líneas, cada una con un entero, la solución del problema para cada caso.

Ejemplo de entrada:

6
1
2
3
4
5
10000

Ejemplo de salida:

1
2
5
8
14
46047940