Satish wants to organize a dance party at IIIT BH-2 but unfortunately he has no money for it
So he plan for funding from all boys to conduct party
So he will move across the hostel rooms to collect fund money
But there is a problem
In this hostel we have two community btech and mtech if he will collect money from btech then no one from mtech will pay and if mtech guys will pay then no one from btech will pay
And all community members will be in this circular shaped hostel in a special manner

if mtech guys pay then no one mtech guy will be neighbour of other mtech guy

if btech guys pay then no one btech guy will be neighbour of other btech guy

Satish wants more money for fund so he approaches to you for his help in money collection.

Input :
First line will be number of test cases t ,each t lines will have two lines first line will be total number of rooms in particular test case and second line will have n space separated integers A[i], which will be money from any individual ith rooms

Output:
t lines each line will have total collection of money from the hostel.

Constraints:

1 ≤ t ≤ 100

1 ≤ n ≤ 10^6

0 ≤ A[i] ≤ 10^5

SAMPLE INPUT
2
3
1 2 3
4
1 2 3 4

SAMPLE OUTPUT
3
6

见题面

见题面