Given a positive integer array $A$ of length $n$, where all numbers are arranged in a row from left to right.

You need to color each number in $A$ either red or blue, and then calculate the final score as follows: Let $C$ be an integer array of length $n$. For each number $A_i$ ($1 \le i \le n$) in $A$: If there is no number of the same color to the left of $A_i$, then $C_i = 0$. Otherwise, let $A_j$ be the closest number of the same color to the left of $A_i$. If $A_i = A_j$, then $C_i = A_i$; otherwise, $C_i = 0$.

Your final score is the sum of all integers in $C$, i.e., $\sum_{i=1}^{n} C_i$. You need to maximize the final score. Please find the maximum possible value of the final score.

Input

The input is read from the file color.in. This problem contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. Each test case is formatted as follows: The first line contains a positive integer $n$, representing the length of the array. The second line contains $n$ positive integers $A_1, A_2, \dots, A_n$, representing the elements of array $A$.

Output

The output is written to the file color.out. For each test case: output a single line containing a non-negative integer, representing the maximum possible value of the final score.

Examples

Input 1

3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4

Output 1

1
0
8

Note

For the first test case, here are three possible coloring schemes: 1. Color $A_1, A_2$ red, and $A_3$ blue ($1, 2, 1$), the score is calculated as follows: For $A_1$, since there is no red number to its left, $C_1 = 0$. For $A_2$, the closest red number to its left is $A_1$. Since $A_1 \neq A_2$, $C_2 = 0$. For $A_3$, since there is no blue number to its left, $C_3 = 0$. The final score for this scheme is $C_1 + C_2 + C_3 = 0$. 2. Color $A_1, A_2, A_3$ all red ($1, 2, 1$), the score is calculated as follows: For $A_1$, since there is no red number to its left, $C_1 = 0$. For $A_2$, the closest red number to its left is $A_1$. Since $A_1 \neq A_2$, $C_2 = 0$. For $A_3$, the closest red number to its left is $A_2$. Since $A_2 \neq A_3$, $C_3 = 0$. The final score for this scheme is $C_1 + C_2 + C_3 = 0$. 3. Color $A_1, A_3$ red, and $A_2$ blue ($1, 2, 1$), the score is calculated as follows: For $A_1$, since there is no red number to its left, $C_1 = 0$. For $A_2$, since there is no blue number to its left, $C_2 = 0$. * For $A_3$, the closest red number to its left is $A_1$. Since $A_1 = A_3$, $C_3 = A_3 = 1$. The final score for this scheme is $C_1 + C_2 + C_3 = 1$.

It can be proven that no coloring scheme results in a final score greater than 1.

For the second test case, it can be proven that the final score for any coloring scheme is 0.

For the third test case, an optimal coloring scheme is to color $A_1, A_2, A_4, A_5, A_7$ red, and $A_3, A_6, A_8$ blue ($3, 5, 1, 5, 2, 1, 2, 4$), which corresponds to $C = [0, 0, 0, 5, 0, 1, 2, 0]$, and the final score is 8.

Constraints

For all test cases, it is guaranteed that: $1 \le T \le 10$, $2 \le n \le 2 \times 10^5$, $1 \le A_i \le 10^6$.