Бинарная строка — это строка, состоящая из символов \(0\) и \(1\). Би-таблица — это таблица, состоящая из ровно двух бинарных строк одинаковой длины.
Определим \(\operatorname{MEX}\) би-таблицы как наименьшую из цифр \(0\), \(1\) или \(2\), которая не встречается в этой би-таблице. Например, \(\operatorname{MEX}\) для \(\begin{bmatrix} 0011\\ 1010 \end{bmatrix}\) — это \(2\), потому что \(0\) и \(1\) встречаются хотя бы один раз. \(\operatorname{MEX}\) для \(\begin{bmatrix} 111\\ 111 \end{bmatrix}\) — это \(0\), потому что \(0\) и \(2\) не встречаются ни разу, и \(0 < 2\).
Дана би-таблица с \(n\) столбцами. Необходимо разбить её на произвольное количество би-таблиц (каждая состоит из последовательных столбцов) так, чтобы каждый её столбец принадлежал ровно одной би-таблице. Би-таблицу разрешается разбить на одну би-таблицу — её саму.
Какую максимальную сумму \(\operatorname{MEX}\) всех полученных би-таблиц можно получить?
Выходные данные
Для каждого набора входных данных выведите единственное целое число — наибольшую сумму \(\operatorname{MEX}\), которую можно получить, разбив би-таблицу оптимально.
Примечание
В первом наборе входных данных би-таблицу можно разбить следующим образом:
- \(\begin{bmatrix} 0\\ 1 \end{bmatrix}\), \(\operatorname{MEX}\) равен \(2\).
- \(\begin{bmatrix} 10\\ 10 \end{bmatrix}\), \(\operatorname{MEX}\) равен \(2\).
- \(\begin{bmatrix} 1\\ 1 \end{bmatrix}\), \(\operatorname{MEX}\) равен \(0\).
- \(\begin{bmatrix} 0\\ 1 \end{bmatrix}\), \(\operatorname{MEX}\) равен \(2\).
- \(\begin{bmatrix} 0\\ 0 \end{bmatrix}\), \(\operatorname{MEX}\) равен \(1\).
- \(\begin{bmatrix} 0\\ 0 \end{bmatrix}\), \(\operatorname{MEX}\) равен \(1\).
Сумма \(\operatorname{MEX}\) равна \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
0101000
1101100
5
01100
10101
2
01
01
6
000000
111111
|
8
8
2
12
|