题目描述

初始有一个空的 01 串，每步操作可以将 0 或 1 添加在左侧或右侧。也可以对整个串进行反异或操作：取 $s' = s \oplus rev(s)$，其中 $s$ 是目前的 01 串，$\oplus$ 表示逐位异或，$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| \leq 10$；

对于 $40\%$ 的评测用例，$|T| \leq 500$；

对于 $60\%$ 的评测用例，$|T| \leq 5000$；

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

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