Dado un entero positivo ~n~, Se le ha pedido que calcule la siguiente suma de la manera eficiente:

~ \sum_{k=1}^{n}\frac{n}{gcd(n,k)} ~

Aquí ~gcd (a, b)~ significa máximo común divisor de dos enteros ~a~ y ~b~.

Por razones clasificadas se decidió dar una pista importante, tras alguna observación/transformación china, la anterior fórmula se reduce a:

~ \sum_{k\in{d(n)}}k \cdot \phi(k) ~

Donde ~d(n)~ significa todos los divisores de ~n~, incluyendo ~1~ y ~n~. Y ~\phi(n)~ significa la cantidad de números ~x~, coprimos con ~n~, tal que ~1 \leq x \leq n~, conocido como Euler totient function.

Entrada

La primera línea de entrada contiene un número entero ~T~ ~(1 \le T \le 10^6)~ que indica el número de casos de prueba. A continuación se muestra la descripción de los ~T~ casos de prueba. La única línea que describe cada caso de prueba contiene un solo entero ~n~, ~(1 \le n \le 10^7)~. Tenga en cuenta que la entrada puede ser muy grande. Por lo que se recomienda utilizar métodos Input/Output rápidos.

Salida

Para cada caso de prueba, genere una sola línea que contenga un entero: respuesta a la consulta.

Puntuación

• Subtarea 1 (10 ptos): ~T \leq 10~, ~n_{i} \leq 2 \cdot 10 ^ 5~.
• Subtarea 2 (30 ptos): ~T \leq 2 \cdot 10 ^ 5~, ~n_{i} \leq 2 \cdot 10 ^ 5~.
• Subtarea 3 (60 ptos): Sin restricciones adicionales.

Ejemplos

Entrada

5
1
2
3
4
5

Salida

1
3
7
11
21