지하철

스위스 로잔에는 현대적인 지하철이 있습니다. 그중 M1 노선은 단선(하나의 선로)이면서도 양방향으로 운행하는 독특한 구조입니다. 열차는 하나의 선로 위를 양쪽 방향으로 달리며, 선로가 잠깐 두 갈래로 갈라지는 승강장이 두 개인 역에서 서로 교행합니다.

이 문제에서는 로잔의 M1과 비슷한 지하철 노선을 생각합니다. 노선은 하나의 선로로 이어진 $N$개의 역으로 이루어집니다. 1번 역은 2번 역과, 2번 역은 1번 역 및 3번 역과, 3번 역은 2번 역 및 4번 역과 연결되는 식으로 일렬로 놓여 있습니다. 이웃한 두 역 사이의 거리는 모두 같고, 열차가 이웃한 두 역 사이를 이동하는 데는 정확히 1분이 걸립니다.

일부 역은 승강장이 두 개라서, 서로 반대 방향으로 달리는 두 열차가 그곳에서 안전하게 마주쳐 지나갈 수 있습니다. 나머지 역은 승강장이 하나뿐이라, 그런 역에서 두 열차가 마주치면 충돌 사고가 납니다.

노선의 양쪽 끝에서 두 열차가 서로 반대 방향을 향해 동시에 출발합니다. 두 열차가 오직 승강장이 두 개인 역에서만 서로를 지나치도록, 원하는 역에 원하는 만큼(0 이상의 정수 분) 추가 정차를 배정할 수 있습니다. 승강장이 두 개인 역에서는 두 열차가 양쪽에서 동시에 들어와도 되고, 한 열차가 그 역에서 다른 열차를 기다려도 됩니다.

충돌 없이 운행할 때 필요한 최소 운행 시간은 얼마입니까? 최소 운행 시간이란, 두 열차가 모두 온전하게 서로 반대편 끝 역에 도착해 운행을 마치기까지 걸리는 최소 시간을 뜻합니다. 한 열차가 먼저 도착하면, 나중에 도착하는 열차의 도착 시각이 곧 답이 됩니다.

첫째 줄에 테스트 세트의 개수를 나타내는 자연수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 각 테스트 세트가 차례로 주어집니다.

각 테스트 세트는 두 줄로 이루어집니다. 첫째 줄에는 역의 개수를 나타내는 양의 정수 $N$ ($2 \le N \le 10^6$)이 주어집니다. 둘째 줄에는 각 역의 승강장 수를 나타내는 $N$개의 양의 정수 $s_i$가 공백 하나로 구분되어 역의 순서대로 주어집니다. 각 $s_i$는 $1$ 또는 $2$이며, $i$번째 역의 승강장 개수를 뜻합니다. 승강장이 두 개인 역은 적어도 하나 존재합니다.

각 테스트 세트마다 충돌 없이 운행할 수 있는 최소 운행 시간을 한 줄에 하나씩 출력합니다. 답의 순서는 입력에 주어진 테스트 세트의 순서와 같아야 합니다.