Definition

A sequence $v = (a_1,a_2,a_3)$ consisting of 3 elements is said to be a Kadomatsu sequence if $v$ satisfies the following conditions.

1. $a_1,a_2,a_3$ are all distinct
2. Among the 3 elements, $a_2$ is the largest or the smallest

Problem Statement

$N$ integers $A_1,\ldots,A_N$ are arranged clockwise in a circle.
Seen from the center of the circle, the right neighbor of $A_i$ is $A_{i+1}$. Also, the right neighbor of $A_N$ is $A_1$.

If the sequence obtained by taking some 3 consecutive elements in their original order is a Kadomatsu sequence, they can be made into a group.
Each element can belong to at most one group; it cannot belong to two or more groups.

Here, the score of a group is defined as the value of the leftmost integer among its 3 elements, as seen from the center of the circle.
Output the maximum possible sum of the scores of the groups when the groups are formed appropriately.
If no groups are formed, the sum of the scores of the groups is $0$.

Input

A single input may contain multiple test cases.

The first line gives the number of test cases $T$.
Each test case is then given in the following 2 lines each.

$T$
$N_1$
$A_{1,1}\ \ldots\ A_{1,N_1}$
$\vdots$
$N_T$
$A_{T,1}\ \ldots\ A_{T,N_T}$

$1 \le T \le 2\times 10^4$
$3 \le N_j \le 2\times 10^5$
$1\le A_{j, i} \le 2\times 10^5$
$\sum_{j\in 1\ldots T}N_j \le 2\times 10^5$

All values in the input are integers.

Output

For each test case, output the maximum sum of the scores of the groups, separated by newlines.
Add a newline at the end.

Sample

3
3
1 2 3
6
2 1 99 2 3 1
4
1 1 1 1

3
99
0