Metro

In the Swiss city of Lausanne there is a modern metro. One of its lines, M1, is single-track yet runs in both directions: trains travel both ways along a single track and pass each other at two-platform stations, where the track briefly splits into two.

In this problem we consider a metro line similar to Lausanne's M1. The line consists of $N$ stations joined by a single track: station 1 is connected to station 2, station 2 to stations 1 and 3, station 3 to stations 2 and 4, and so on, forming a straight path. The distances between neighbouring stations are all equal, and a train always takes exactly one minute to travel between two neighbouring stations.

Some stations have two platforms, so two trains heading in opposite directions can meet and pass each other there safely. The remaining stations have a single platform, and two trains meeting at such a station would collide.

Two trains set off at the same moment from the two ends of the line, heading in opposite directions. You may assign the trains extra stops (of any length, given as a non-negative whole number of minutes) at any stations, so that the trains pass each other only at a two-platform station. At a two-platform station the two trains may enter simultaneously from both sides, or one train may wait there for the other.

What is the minimum travel time that avoids any collision? By minimum travel time we mean the smallest time by which both trains, intact, have finished their journeys at the opposite ends of the track. If one train finishes earlier, the answer is the arrival time of the later train.

The first line contains a natural number $Z$ ($1 \le Z \le 10$), the number of test sets. The test sets then follow one after another.

Each test set consists of two lines. The first line contains a positive integer $N$ ($2 \le N \le 10^6$), the number of stations. The second line contains $N$ positive integers $s_i$ separated by single spaces, given in order for the stations. Each $s_i$ is $1$ or $2$ and gives the number of platforms at station $i$. At least one station has two platforms.

For each test set, print the minimum collision-free travel time on its own line. The answers must appear in the same order as the test sets in the input.