It's that time of the year again! The children in Christmas town is celebrating the coming of the Christmas and waiting for their gift from Santa.
On the other hand, Santa and his elves aren't so happy. They have been overworked, preparing their gifts and making note who had been good enough the past year to receive a gift. Their final task, which has been delegated to you, is to plan how to deliver those gifts in the most efficient way possible.
There are N houses in Christmas town, all lined up in a straight line. These houses are labeled from 0 to N-1. Santa will visit each household that is suppose to receive gift and drop off ALL the gifts before moving onto the next house. The time it takes to drop off the gifts is equal to the number of gifts to drop off.
Now, Santa had been very studious last year and went to Japan to learn the way of Ninjas. One of the techniques he learned was instant teleportation. Thus, it does not take Santa any time to travel between houses (only the time to drop off the gift). Santa has also learned the way of cloning himself, so he can make up to 1 copy of himself (ie. there are at most 2 santas at any given time). Your task is to calculate how much time is required for Santa to deliver all the gifts to Christmas town.
Finally, as a safety precaution, it is IMPORTANT that the Santa and his clone are NEVER in the same house at any given time. This is so that children who are awake and trying to peek at Santa won't see two of them.
The first line of the input is t, indicating the number of test cases to follow. Each test case consists of two lines. The first line of each test case is an integer N, N less than or equal to 15. The next line consist of N integers, ranging from 0 to 3, representing how many gifts each household is suppose to have. The ith number represent how much gift the ith house is suppose to receive (0 means no gift).
For each test case, output how much time Santa must spend in Christmas town distributing gifts on a separate line.
3
5
0 2 3 2 0
3
2 2 2
2
2 2
4
4
2
Explanation: In the first test case, the real Santa will distribute gift at house 1,
then at house 3 while the clone distribute gift at house 2. The
clone will finish after 3 and the real Santa after
4. Note that we do not need so spend time at house 0 and
4. Also, the clone could not help Santa distribute gift at
house 3.
In the second test case, either the real Santa or the clone
must drop off the gifts at 2 households, taking up a total of
4 units of time.