定義

3つの要素から成る数列$v = (a_1,a_2,a_3)$が次の条件を満たす時、$v$は門松列であると言い伝えられています。

1. $a_1,a_2,a_3$は全て異なる
2. 3つの要素のうち$a_2$が最も大きい、あるいは最も小さい

問題文

$N$ 個の整数 $A_1,\ldots,A_N$ が時計回りに円状に並んでいます。
円の中心から見て $A_i$ の右隣は $A_{i+1}$ です。また、$A_N$ の右隣は $A_1$ です。

ある連続する3要素を元の順序で並べた列が門松列であるならば、それらをグループにすることができます。
各要素が属することができるのは高々1つのグループであり、2つ以上のグループに属することはできません。

ここで、グループの評価値を3要素のうち円の中心から見て左端の整数の値とします。
適切にグループを作成したときのグループの評価値の総和の最大値を出力してください。
なお、グループを作成しない場合、グループの評価値の総和は $0$ とします。

入力

1つの入力に複数のテストケースが含まれる場合があります。

1行目にテストケースの個数 $T$ が与えられます。
続く各2行ごとに、各テストケースが与えられます。

$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$

入力に含まれる値はすべて整数である。

出力

各テストケースにおけるグループの評価値の総和の最大値を改行区切りで出力してください。
最後に改行してください。

サンプル

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

3
99
0