You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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.