NIT Jsr Champions League is going on in the campus. So, after qualifying in the group stage N teams have made it to the knockout stage. Each teams will compete with its adjacent team and the winner will move to the next round.

You are given an array A consisting of N integers denoting the strength of each team. The team with the higher strength wins. In case of tie, one of the team will advance to the next round randomly. Matches between the teams will be played from left to right.

You have to tell the sum of values of the teams that will qualify.

Note: N will be an even integer.

Input:

First line of Input contains T denoting the number of testcases.

First line of each testcase contains N denoting the number of teams. 

Second line of each testcase contains N integers denoting the strength of each team.

Output:

For each testcase a single integer denoting the required answer each in a separate line.

Constraints:

1 <=T <=1000

N is even

1 <=N <=500

1 <= Strength of each team <=1000

Problem Setter:

Shikhar Kunal