Изначально у Тимура есть бинарная строка \(^{\dagger}\) \(s\) (возможно длины \(0\)). Он применил следующую операцию несколько раз (возможно ноль):
- Приписать \(\texttt{0}\) к одному из концов строки и \(\texttt{1}\) к другому концу строки. Например, из строки \(\texttt{1011}\), мы можем получить или \(\color{red}{\texttt{0}}\texttt{1011}\color{red}{\texttt{1}}\), или \(\color{red}{\texttt{1}}\texttt{1011}\color{red}{\texttt{0}}\).
Вам дана строка, которая получилась у Тимура. Какая наименьшая возможная длина строки могла быть вначале (до выполнения всех операций)?
\(^{\dagger}\) Бинарная строка это строка (возможно пустая), содержащая только символы \(\texttt{0}\) или \(\texttt{1}\).
Выходные данные
Для каждого набора входных данных выведите единственное неотрицательное целое число — наименьшую возможную длину изначальной строки Тимура. Обратите внимание, что изначальная строка Тимура может быть пустой, в этом случае выведите \(0\).
Примечание
В первом наборе входных данных, кратчайшая изначальная строка Тимура это \(\texttt{0}\). К ней он применил следующую операцию: \(\texttt{0} \to \color{red}{\texttt{1}}\texttt{0}\color{red}{\texttt{0}}\).
Во втором наборе, кратчайшая изначальная строка Тимура это \(\texttt{11}\). К ней он применил следующую операцию: \(\texttt{11} \to \color{red}{\texttt{0}}\texttt{11}\color{red}{\texttt{1}}\).
В третьем наборе, кратчайшая изначальная строка Тимура это \(\texttt{10101}\) и он не применял к ней никаких операций.
В четвертом наборе, кратчайшая изначальная строка Тимура это пустая строка (обозначим её как \(\varepsilon\)). К ней он применил следующие операции: \(\varepsilon \to \color{red}{\texttt{1}}\texttt{}\color{red}{\texttt{0}} \to \color{red}{\texttt{0}}\texttt{10}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{0101}\color{red}{\texttt{0}}\).
В пятом наборе, кратчайшая изначальная строка Тимура это \(\texttt{101}\). К ней он применил следующие операции: \(\texttt{101} \to \color{red}{\texttt{0}}\texttt{101}\color{red}{\texttt{1}} \to \color{red}{\texttt{1}}\texttt{01011}\color{red}{\texttt{0}}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010
|
1
2
5
0
3
1
0
2
4
|