Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

K. Helping Eagle
time limit per test
1 second
memory limit per test
256 megabytes
input
help.in
output
standard output

Your friend Eagle is playing a game.

In this game, Eagle has an array $$$A$$$ of $$$N$$$ positive integers.

In the first turn, Eagle chooses any index $$$i$$$ to start with and adds $$$A_i$$$ to his score.

Starting from the next turn, assuming that the last chosen index was index $$$i$$$. Eagle chooses any index $$$j$$$ such that $$$j$$$ wasn't chosen before and $$$|j-i| \leq 2$$$ then adds $$$A_j$$$ to his score.

Before the game starts you had a chance to choose two indices to block them such that Eagle can't choose them (at the beginning or during the game).

You would like to minimize Eagle's score if he plays optimally.

Input

The first line of the input contains one integer $$$T$$$ $$$(1 \leq T \leq 2*10^5)$$$ the number of test cases.

Each test case consists of two lines:

First line contains one number $$$N$$$ $$$(3 \leq N \leq 2 \times 10^5)$$$ the length of the array $$$n$$$.

The second line contains $$$N$$$ integers $$$A_1, A_2 \dots A_n$$$ $$$(1 \leq A_i \leq 10^9)$$$.

The total sum of $$$N$$$ over all test cases doesn't exceed $$$2 \times 10^5$$$.

Output

For each test case, output one integer, the minimum score that Eagle gets if he plays optimally.

Example
Input
2
5
1 1 1 1 1
3
10 15 4
Output
2
4