C. Mortal Kombat Tower
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы и ваш друг играете в Mortal Kombat XI. Вы пытаетесь пройти башню испытаний. Всего в башне есть $$$n$$$ боссов, пронумерованных от $$$1$$$ до $$$n$$$. Тип $$$i$$$-го босса равен $$$a_i$$$. Если $$$i$$$-й босс является легким, то его тип равен $$$a_i = 0$$$, иначе этот босс является сложным и его тип равен $$$a_i = 1$$$.

В течение одной игровой сессии вы или ваш друг можете убить одного или двух боссов (ни вы, ни ваш друг не можете пропускать сессию, поэтому минимальное количество боссов, убитых в течение сессии, равно хотя бы одному). После сессии вашего друга начинается ваша сессия, затем опять сессия вашего друга, затем опять ваша, и так далее. Первая сессия — сессия вашего друга.

Вашему другу надо научиться играть лучше, потому что на самом деле он не может убивать сложных боссов. Чтобы убивать их, он использует очки пропуска. Одно очко пропуска может быть использовано для того, чтобы убить одного сложного босса.

Ваша задача — найти минимальное количество очков пропуска, которое ваш друг должен использовать для того, чтобы вы с вашим другом убили всех $$$n$$$ боссов в заданном порядке.

Например: предположим, что $$$n = 8$$$, $$$a = [1, 0, 1, 1, 0, 1, 1, 1]$$$. Тогда лучшей последовательностью действий является следующая:

  • ваш друг убивает первых двух боссов, используя одно очко пропуска для первого босса;
  • вы убиваете третьего и четвертого боссов;
  • ваш друг убивает пятого босса;
  • вы убиваете шестого и седьмого боссов;
  • ваш друг убивает последнего босса, используя одно очко пропуска, таким образом, башня проходится с использованием двух очков пропуска.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество боссов. Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$), где $$$a_i$$$ равно типу $$$i$$$-го босса.

Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Выходные данные

Выведите ответ на каждый набор тестовых данных: минимальное количество очков пропуска, которое ваш друг должен использовать для того, чтобы вы с вашим другом убили всех $$$n$$$ боссов в заданном порядке.

Пример
Входные данные
6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0
Выходные данные
2
2
2
2
1
0