Candy Factory

A candy factory has $n$ rooms for making candy. $n$ is odd and $3 \le n \le 1001$. Each room makes exactly one kind of candy, and the rooms are numbered 1 through $n$.

Room 1 makes the ultimate candy. One piece of that special candy comes from mixing one candy from room 2 with one candy from room 3. A candy from room 2 is itself a mix of one candy from room 4 and one candy from room 5, and a candy from room 3 is a mix of one candy from room 6 and one candy from room 7. In general, room $i$ ($1 \le i \le \lfloor n/2 \rfloor$) takes one candy from room $2i$ and one candy from room $2i+1$ as the ingredients for one candy of its own. Every kind of candy therefore ends up inside the ultimate candy from room 1.

Each room makes as many candies as its ingredients allow, so the count for room $i$ is decided by how many candies rooms $2i$ and $2i+1$ still hold. Take a factory with 3 rooms. If room 2 made 5 candies and room 3 made 7, then room 1 makes 5 ultimate candies. Room 3 is left with 2 candies and room 2 is left with none, so the factory made 7 candies in total.

Rooms $\lfloor n/2 \rfloor + 1$ through $n$ make candy without ingredients, and the amount each of them made is given. Find how many candies the factory made in total. The total adds up the candies made in every room and then subtracts the candies from rooms $2i$ and $2i+1$ that room $i$ consumed as ingredients.

The first line has the number of test cases. Each test case then takes two lines. The first line has $n$, the number of candy rooms in the factory. The second line has the number of candies made in rooms $\lfloor n/2 \rfloor + 1$ through $n$, listed in room order, so there are $\lfloor n/2 \rfloor + 1$ values. Every following pair of lines is the next test case.

Print one line per test case. Each line holds the total number of candies the factory made for that test case.