Las competencias atléticas en las escuelas algunas veces se vuelven muy controversiales y competitivas. Para promover el trabajo en equipo, los profesores han creado un juego donde la cooperación lleva a obtener mejores puntuaciones. Este juego comienza con ~N~ estudiantes parados en una línea. Para obtener una puntuación, dos estudiantes de la misma aula saldrán de la línea. Si ellos eran los estudiantes número ~i~ y ~j~, añaden ~|i - j|~ a la puntuación total. Los lugares vacíos de los dos estudiantes que acaban de salir serán compactados. El juego finaliza cuando no hay más pares de estudiantes de la misma aula. Por ejemplo, considera seis estudiantes inicialmente parados en una línea: $$\displaystyle 1, 2, 3, 3, 2, 1$$ Los números son los números de las aulas de los estudiantes. Si los estudiantes salen de la línea en el orden: aula número 1, luego aula número 2, luego aula número 3, la puntuación total es 5 + 3 + 1 = 9. Sin embargo, en la misma situación inicial, si los estudiantes salen de la línea en el orden 3, 2, 1, entonces la puntuación total es 1 + 1 + 1 = 3. Dados los números de las aulas en la línea inicial, escribe un programa que calcule la mayor puntuación posible.

Entrada

La primera línea contiene un entero ~T~, el número de casos de prueba (~1 \le T \le 48~). Los casos de prueba siguen: La primera línea de cada caso contiene un entero ~N~, el número de estudiantes (~1 \le N \le 3\cdot 10^5~). En la siguiente línea aparecen los números de las aulas. Los números de las aulas son enteros desde ~1~ hasta ~N~. La suma de ~N~ sobre todos los casos no excede ~7\cdot 10^6~.

Salida

Para cada caso de prueba, imprime una línea con un entero: la mayor puntuación posible.

Subtareas

• Subtarea 1 (10 puntos): Todos los estudiantes pertenecen a la misma aula.

• Subtarea 2 (20 puntos): Los números de las aulas de los estudiantes están en orden ascendente.

• Subtarea 3 (20 puntos): Para cada aula, hay exactamente dos estudiantes pertenecientes a ella. ~N~ es par.

• Subtarea 4 (25 puntos): ~N \leq 5000~. La suma de ~N~ sobre todos los casos no excede 5000.

• Subtarea 5 (25 puntos): Sin restricciones adicionales.

Ejemplos de entrada y salida

Entrada 1

2
7
1 2 1 1 2 1 2
12
1 2 3 1 2 3 1 2 3 1 2 3

Salida 1

10
30