问题描述

初始有一个空的 01 串，每步操作可以将 0 或 1 添加在左侧或右侧。也可以对整个串进行反异或操作：取 $s′=s⊕rev(s)$，其中 $s$ 是目前的 01 串，⊕ 表示逐位异或，$rev(s)$ 代表将 $s$ 翻转，也就是说取中心位置并交换所有对称的两个位置的字符。例如，$rev(0101)=1010$，$rev(010)=010$，$rev(0011)=1100$。

反异或操作最多使用一次（可以不用，也可以用一次）。

给定一个 01 串 $T$，问最少需要添加多少个 1 才能从一个空 01 串得到 $T$。

在本题中 0 可以添加任意个。

输入格式

输入一行包含一个 01 串表示给定的 $T$。

输出格式

输出一行包含一个整数，表示需要最少添加多少个 1。

样例

00111011

3

评测用例规模与约定

对于 $20\%$ 的评测用例，$∣T∣≤10$；

对于 $40\%$ 的评测用例，$∣T∣≤500$；

对于 $60\%$ 的评测用例，$∣T∣≤5000$；

对于 $80\%$ 的评测用例，$∣T∣≤10^5$；

对于所有评测用例，$1≤∣T∣≤10^6$，保证 $T$ 中仅含 0 和 1。