Dada una secuencia de enteros $a_1, a_2, \cdots, a_n$ de longitud $n$, construimos un grafo no dirigido $G$ a partir de ella. Más precisamente, para todos los $1 \le i < j \le n$, si $i - j = a_i - a_j$, habrá una arista no dirigida en $G$ que conecta los vértices $i$ y $j$. Su peso es $(a_i + a_j)$.
Halla un emparejamiento de $G$ que maximice la suma de los pesos de todas sus aristas e imprime esa suma máxima.
Recuerda que un emparejamiento de un grafo no dirigido consiste en elegir algunas aristas del grafo de modo que ninguna pareja de aristas tenga vértices en común. En particular, no elegir ninguna arista también es un emparejamiento.
Entrada
Hay varios casos de prueba. La primera línea de la entrada contiene un entero $T$ que indica el número de casos de prueba. Para cada caso:
La primera línea contiene un entero $n$ ($2 \le n \le 10^5$) que indica la longitud de la secuencia.
La segunda línea contiene $n$ enteros $a_1, a_2, \cdots, a_n$ ($-10^9 \le a_i \le 10^9$) que indican la secuencia.
Se garantiza que la suma de $n$ de todos los casos de prueba no supera $5 \times 10^5$.
Salida
Para cada caso de prueba, imprime una línea con un entero que indique la máxima suma de los pesos de todas las aristas de un emparejamiento.
Ejemplos
Entrada 1
3 9 3 -5 5 6 7 -1 9 1 2 3 -5 -4 -3 3 1 10 100
Salida 1
30 0 0
Nota
Para el primer caso de prueba del ejemplo, la elección óptima consiste en elegir las tres aristas que conectan los vértices $3$ y $5$, los vértices $4$ y $7$, y los vértices $8$ y $9$. La suma de los pesos es $(5 + 7) + (6 + 9) + (1 + 2) = 30$.
Para el segundo caso de prueba del ejemplo, como todas las aristas tienen pesos negativos, el emparejamiento óptimo no debe elegir ninguna arista. La respuesta es $0$.
Para el tercer caso de prueba del ejemplo, como no hay aristas en el grafo, la respuesta es $0$.