## Rey in Trouble

Time Limit: 5 sec
Memory Limit: 256 MB
Attempts: 0
Accuracy: 0.00%
Author: Akashdeep Goel

We all know how good Young Rey was in flying the Millennium Falcon. But this time she found herself in trouble where she was stuck in the center of N mini death stars arranged in a circle (Nth death star is adjacent to the first one). Each death star has some stormtroopers protecting it. Rey can shoot three adjacent death stars in one shot but after each shot the remaining stormtroopers will cause damage to Rey (one unit per stormtrooper). The process continues until all death stars are destroyed. Help Rey to determine a plan so that she takes minimum damage.

After each shot the remaining death stars donâ€™t become cyclic.

Ex. Let there be 7 death stars and after destroying death stars numbered 3,4,5 in one shot death stars numbered 2 and 6 donâ€™t become adjacent.

INPUT:

The first line contains integer T (T<=50), number of test cases. Then each test case starts with a line that contains integer N, number of death stars, on which stormtroopers have taken a circular defense. 3 â‰¤ N â‰¤ 20. The second line of each test case contains N integers, number of stormtroopers on each balcony (not less than 1 and no more than 100 on each).

OUTPUT:

Output minimum amount of damage that Rey takes for each test case in a new line.

Examples:

Input:

2

5

7 8 3 10 20

7

4 5 3 3 2 5 2

Output:

11

14

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED