Background

学长很喜欢逃课但是运气不好每次都被老师抓住，老师因此对其特别关注.

Description

如果学长逃课了就记录为0，没逃课就记录为1，因此得到一个01字符串表示学长的考勤情况

学长不想挂科于是求老师放放水，老师网开一面给出一个办法

现在学长可以对01字符串进行回文删除操作，要求学长用最少次数将01字符串删除完，学长实际缺勤次数与操作次数的最小值作为最终缺勤次数。

回文删除：选择一个非空的子序列（可以不连续），且此子序列是一个回文的字符串，将这个子序列的所有字符删除

回文字符串：回文字符串是指正读和反读完全相同的字符串，即字符串对称，例如10001和0110.

子序列：子序列为从原字符串中删除（可以不连续）任意个（可以为零）元素得到的新字符串,以10001为例，10，11，10001等都是它的子序列。

Format

Input

第一行输入字符串s(s的长度不超过20且保证只由‘0’和‘1’组成)

Output

输出一个整数表示学长的最终缺勤次数

Samples

10011101

2

提示：逃课三次就不能参与期末考试，老师不会这么绝情的，所以学长肯定可以参与期末考试的

Limitation

1s, 1024KiB for each test case.