兔子是兔形目兔科的小型哺乳动物。维基百科是这样说的。没错。由此得出的推论是，它们并不无聊，因为它们都很有创意且组织严密。我们农场上的兔子生活在有围栏的圈里，圈的边界装饰着精致的花卉图案。圈里生长着许多可爱的橙色胡萝卜丛。兔子繁殖速度很快（每年都有成群的兔子出生是常态），我们的导师们非常渴望能毫不费力地在圈里找到它们。

这些圈的排列井然有序，它们排成一条直线。在第一个繁殖季节开始时，某些圈里可能没有兔子。在每个繁殖季节结束时，会进行一次精心安排的兔子重新安置。重新安置遵循一个简单的规则，该规则取决于一个正整数参数 $K$，每个季节可以任意选择 $K$ 的值。重新安置在所有圈中并行进行。在每个圈中，大约有一半的兔子会被移出，并向着这一排圈的后方（即朝向末尾的方向）移动 $K$ 个圈。目标圈是否已经有兔子并不重要。

如果某个圈距离这一排的末尾太近（即该圈后面剩下的圈数少于 $K$ 个），那么该圈中的所有兔子都将留在原处，不进行任何移动。

任何圈都可以容纳无限数量的兔子，并且在任何非空的圈中，总是有足够的兔子可以成功繁殖。

给你一个在第一个繁殖季节开始时，哪些圈被占用、哪些圈是空着的规格说明。请确定使所有圈都住满兔子所需的最少重新安置次数。

输入格式

输入仅包含一行，为一个长度为 $b$ 的字符串（$1 \le b \le 40$），其中每个字符代表一个圈，字符为 0（表示空圈）或 1（表示有兔子的圈）。第一个字符对应这一排中的第一个圈。

输出格式

输出使所有圈都住满兔子所需的最少重新安置次数。如果无论进行多少次重新安置都无法使所有圈住满兔子，则输出 -1。

样例

输入样例 1

1010

输出样例 1

1

输入样例 2

100110000

输出样例 2

3