Дан массив \(a\) длины \(n\). Каждый элемент массива — \(0\), \(1\) или \(2\). Известно, что нули находятся только строго в левой половине массива, то есть на индесах от \(1\) до \(\left\lfloor\frac{n}{2}\right\rfloor\). Все оставшиеся элементы могут быть равны только \(1\) или \(2\).
С массивом разрешается выполнять следующие два вида действий:
-
Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).
-
Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_i\) копий числа \(a_{i+1}\). То есть, возможны следующие преобразования:
Иными словами, \(0\) можно удалить вместе со следующим числом, \(1\) можно удалить саму по себе, если она стоит не в конце массива, а \(2\) можно заменить на следующее за ней число.
Определите, какое минимальное число монет требуется заплатить, чтобы превратить данный массив в пустой. Обратите внимание, что ответ всегда существует, потому что можно просто \(n\) раз применить первую операцию.
Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.
Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(0 \le a_i \le 2\)).
Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).
Формат выходных данных
Выведите \(T\) целых чисел, каждое в своей строке — ответы на задачу для каждого набора входных данных в том порядке, в котором оны даны во вводе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
0 2 0 1 1 2 2
5
1 1 1 1 1
11
0 1 2 2 0 1 2 2 1 2 1
10
1 2 1 2 0 2 2 2 2 1
|
5
6
9
11
|