定義

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

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

問題文

$N$ 個の整数 $A_1,\dots ,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}\dots A_{1,N_1}$
$⋮$
$N_T$
$A_{T,1}\dots 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\dots 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