你有 $n$ 盏排成一行的灯，每盏灯都有一个对应的按钮。按下某盏灯的按钮会切换该灯的状态；如果灯是亮的，它会熄灭；如果灯是灭的，它会点亮。灯的状态在每个 1 秒的时间步长发生变化。你可以在任何时间按下按钮，但它要到下一个时间步长才会生效。在每个时间步长之前，你可以选择至多按下一个按钮（你也可以选择不按任何按钮）。

按下按钮不仅会影响该灯，还会影响该灯之后的所有灯。具体来说，如果你选择在第 $k$ 个时间步长之前按下第 $i$ 个按钮，那么第 $(i+m)$ 盏灯将在第 $(k+m)$ 个时间步长切换状态（其中 $i+m \le n$）。例如，如果你在时间 19 之前按下第 5 个按钮，那么第 5 盏灯将在时间 19 切换，第 6 盏灯将在时间 20 切换，第 7 盏灯将在时间 21 切换，依此类推。如果你按下的按钮所产生的影响与之前按下的按钮导致该灯切换的时间重合，那么这两次切换会相互抵消，包括后续的连锁切换。

假设有三盏灯，开始时全部处于熄灭状态。如果你在第一个时间步长之前按下第一个按钮，这将在三个时间步长内发生：

现在，假设你在第一个时间步长之前按下第一个按钮，然后在第一个和第二个时间步长之间按下第二个按钮。按钮按下操作将抵消传播，情况如下（注意传播不会进一步进行）：

现在，假设你在第一个时间步长之前按下第一个按钮，然后在第一个和第二个时间步长之间按下第三个按钮。所有三盏灯将在第二个时间步长时全部点亮（但在第三个时间步长时不会）：

你希望点亮所有的灯。你能看到所有灯都点亮的最早时间是多少？注意，如果灯在时间 $t$ 全部点亮，但由于这种传播导致在时间 $t+1$ 时不再全部点亮，那么 $t$ 仍然是正确答案。

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个测试用例包含一个字符串 $S$ ($1 \le |S| \le 16$)。字符串 $S$ 仅包含字符 1 和 0，其中 1 表示该灯初始为亮，0 表示该灯初始为灭。第一个字符对应第 1 盏灯，第二个字符对应第 2 盏灯，依此类推。

输出格式

输出一个整数，表示所有灯都点亮的最早时间。

样例

样例输入 1

1101

样例输出 1

1

样例输入 2

1

样例输出 2

0

样例输入 3

000

样例输出 3

2