Вы и ваш друг играете в 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\) независимых наборов тестовых данных.
Выходные данные
Выведите ответ на каждый набор тестовых данных: минимальное количество очков пропуска, которое ваш друг должен использовать для того, чтобы вы с вашим другом убили всех \(n\) боссов в заданном порядке.