Бинарная строка — это строка, состоящая из символов \(0\) и \(1\).
Определим \(\operatorname{MEX}\) бинарной строки как наименьшую из цифр \(0\), \(1\) или \(2\), которая не встречается в этой строке. Например, \(\operatorname{MEX}\) строки \(001011\) — это \(2\), потому что \(0\) и \(1\) встречаются хотя бы один раз. \(\operatorname{MEX}\) строки \(1111\) — это \(0\), потому что \(0\) и \(2\) не встречаются ни разу, и \(0 < 2\).
Дана бинарная строка \(s\). Необходимо разбить её на произвольное количество подстрок так, чтобы каждая её цифра принадлежала ровно одной подстроке. Строку разрешается разбить на одну подстроку — эту строку целиком.
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Какую минимальную сумму \(\operatorname{MEX}\) всех полученных подстрок можно получить?
Выходные данные
Для каждого набора входных данных выведите единственное целое число — наименьшую сумму \(\operatorname{MEX}\), которую можно получить, разбив \(s\) на подстроки оптимально.
Примечание
В первом наборе входных данных минимальная сумма равна \(\operatorname{MEX}(0) + \operatorname{MEX}(1) = 1 + 0 = 1\).
Во втором наборе входных данных минимальная сумма равна \(\operatorname{MEX}(1111) = 0\).
В третьем наборе входных данных минимальная сумма равна \(\operatorname{MEX}(01100) = 2\).