初始有一個(gè)空的 01 串，每步操作可以將 0 或 1 添加在左側(cè)或右側(cè)。也可以對(duì)整個(gè)串進(jìn)行反異或操作: 取 s ′ = s ⊕ rev(s)，其中 s 是目前的 01 串，⊕ 表示逐位異或，rev(s) 代表將 s 翻轉(zhuǎn)，也就是說取中心位置并交換所有對(duì)稱的兩個(gè)位置的字符。例如，rev(0101) = 1010 rev(010) = 010 rev(0011) = 1100。

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

給定一個(gè) 01 串 T，問最少需要添加多少個(gè) 1 才能從一個(gè)空 01 串得到 T。

在本題中 0 可以添加任意個(gè)。

輸入一行包含一個(gè) 01 串表示給定的 T 。

輸出一行包含一個(gè)整數(shù)，表示需要最少添加多少個(gè) 1 。

對(duì)于 20% 的評(píng)測(cè)用例，|T| ≤ 10 ；

對(duì)于 60% 的評(píng)測(cè)用例，|T| ≤ 5000 ；

對(duì)于 80% 的評(píng)測(cè)用例，|T| ≤ 10⁵ ；

對(duì)于所有評(píng)測(cè)用例，1 ≤ |T| ≤ 10⁶，保證 T 中僅含 0 和 1 。