D - Collar de perlas - II

Time limit: 5 s
Memory limit: 256 MiB
Languages: C, C++, Java, Haskell, ... (details)

Fito le compró a su novia Ana un collar. El collar está compuesto de $N$ perlas donde cada una está numerada con un entero diferente entre $1$ y $N$. Con la intención de hacer el regalo por todo lo alto, Fito decidió reordenar las perlas de forma tal que maximice la belleza del collar. La belleza del collar se define como la suma de la multiplicación de los números en perlas adyacentes. Por ejemplo, si $N=5$ la mejor forma de ubicar las perlas se muestra en la siguiente figura:

Nota que el valor de belleza del collar anterior es $1∗2+2∗4+4∗5+5∗3+3∗1=48$, y $48$ es en efecto el mayor valor de belleza que puede tomar un collar con $5$ perlas. Como la cantidad de perlas puede ser demasiado grande, Fito solamente te ha pedido que calcules el mayor valor de belleza que se puede obtener reordenando las $N$ perlas del collar.

Input

Línea 1 : Un entero $T$ $(1 \le T \le 10^6)$ la cantidad de instancias del problema.
Línea 2…T+1 : Un entero $N$ $(3 \le N \le 2*10^6)$ por línea indicando la cantidad de perlas en el collar.

Output

Línea 1…T : El mayor valor de belleza que se puede obtener para el collar correspondiente.

Sample test(s)

Input
2 5 3
Output
48 11