Se te da una secuencia de enteros de longitud $n$: $a_1, a_2, \dots, a_n$. Puedes realizar la siguiente operación exactamente una vez:

• Elegir una permutación $p_1, p_2, \dots, p_n$ de $1, 2, \dots, n$.
• Luego, para $i$ desde $1$ hasta $n$ en el orden natural, ejecutar: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ donde $a_0 = 0$ y $a_{n+1} = 0$.

Tu objetivo es maximizar la suma de todos los elementos de la secuencia después de que se complete la operación.

Entrada

La primera línea contiene un solo entero $t$ ($1 \le t \le 10^4$), el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene un entero $n$ ($1 \le n \le 2 \cdot 10^5$).

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

La suma de $n$ no supera $2 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con un entero que represente la suma máxima posible de todos los elementos en la secuencia después de realizar la operación.

Ejemplo

Entrada

4
3
1 2 3
4
-1 3 7 6
5
4 1 0 5 2
6
4 -3 7 5 -9 3

Salida

22
85
72
79