背景

在翩翩起舞队的带领下，我们来到了甜苹果庄园。

"只见她低下身子，两只前蹄紧贴地面，腰部一扭，双腿一蹬，两条有力的后腿像子弹一样击打在树干上。随着一声闷响，伴随着树叶的沙沙声，整棵树上的苹果不偏不倚地掉进了篮子里。"其中一只翩翩起舞的小鸟低声说道。

"翩翩，你怎么会有这么多？我会这样说话吗？"我才刚刚升起这个疑问，就被远处传来的苹果杰克的声音打断了。

"这没什么不好的。"另一个弗拉茜冷冷地说，这时苹果杰克篮子里的苹果莫名其妙地一个个飞了起来。

奇怪，为什么有的我竟然会魔法呢？我急忙帮小苹果收起苹果，制止了翩翩起舞的行为。

从形式上看，停止行为可以抽象为以下问题：

给定一个长度为 n 的字符串 s ，它只由 0 和 1 组成。我可以执行以下任意次数的操作：选择 s 和一个正数 k 的子串，然后循环地将子串 k 向左移动位置。

字符串 a 是字符串 b 的子串，当且仅当 a 可以通过删除 b 开头和结尾的某些字符(可以是全部，也可以是一个字符)而得到。

假设有一个字符串s=$s_0$,$s_1$,$s_2$......$s_{(m-2)}$,$s_{(m-1)}$,将它向左移动k，将得到$s_z$,$s_{(z+1)}$.....$s_{(m-1)},$$s_0$,$s_1$.......$s_{(z-2)}$,$s_{(z-1)}$,其中z=kmodm。（mod表示取余操作）

当且仅当 1≤i<n , $s_i$<=$s_{(i+1)}$ 都是0和1时，仅由0和1组成的字符串 s 被排序。在这里，字符是根据其数值进行比较的。

例如，将字符串 0101100 的子串 1011 向左移动两个位置，结果是 0111000。

我需要找出使 s 排序所需的最少操作数。

描述

一行包含仅由 0 和 1 组成的字符串 s ，其中 |s| 表示 s的长度( 1≤|s|≤$10^{5}$ )。

Format

输入

一行包含仅由 0 和 1 组成的字符串 s ，其中 |s| 表示 s 的长度( 1≤|s|≤100000)。( 1≤|s|≤100000 ).

输出

输出一行整数，表示使 s 排序所需的最少操作数

Samples

输入

01010101

输出

3

注释

在第一个例子中，
一个可行的最小操作集是 01010101 
→00110101 → 00011101 → 00001111
其中我们将子字符串 [1,2] 移动了 1 个位置，变成00110101
将子字符串 [2,4] 移动了 2 个位置，变成00011101
将子字符串 [3,6] 移动了 3 个位置，变成00001111。
请注意，字符串索引从 0 开始。

Limitation

1s, 1024KiB for each test case.