题目描述

有一个长为 $N$ 的 01 串 $A$，有两个老哥老 G 和老 T，他们会按照某种方式不断修改这个 01 串。

每一步的流程如下（假设这个串当前的长度为 $L$）：

• 老 G 会去掉当前 01 串的第一个字符，得到一个长为 $L-1$ 的 01 串。
• 老 T 会去掉当前 01 串的最后一个字符，也得到一个长为 $L-1$ 的 01 串。
• 把这个串变成老 G 和老 T 得到的串的 xor。

比如当前的串是 $\texttt{00110}$，老 G 会得到 $\texttt{0110}$，老 T 会得到 $\texttt{0011}$，xor 得到 $\texttt{0101}$。

问经过多少步，这个 01 串不包含字符 $\texttt{1}$。
如果这个 01 串一直有 $\texttt{1}$ 直到变成空串，输出 $-1$。
01 串初始至少有一个 $\texttt{1}$。

输入格式

多组数据，请一直读到文件结束为止。
每组数据一行，一个 01 串。

输出格式

每组数据一行，输出一个答案。

样例

00110

3

• 第一步：

• 开始时的串是 $\texttt{00110}$；
• 老 G 得到的串是 $\texttt{0110}$；
• 老 T 得到的串是 $\texttt{0011}$；
• xor 后得到的串是 $\texttt{0101}$。

• 第二步：

• 开始时的串是 $\texttt{0101}$；
• 老 G 得到的串是 $\texttt{010}$；
• 老 T 得到的串是 $\texttt{101}$；
• xor 后得到的串是 $\texttt{111}$。

• 第三步：

• 开始时的串是 $\texttt{111}$；
• 老 G 得到的串是 $\texttt{11}$；
• 老 T 得到的串是 $\texttt{11}$；
• xor 后得到的串是 $\texttt{00}$。

三步之后这个串全部变成 $\texttt{0}$，所以答案是 $3$。

数据范围与提示

对于所有每个测试点的任何一组数据，数据组数不多于 $7$ 组，$N\leq 8\times 10^6$。
一个测试点的串总长可能很长（不超过 $5.6\times 10^7$），请大家注意读入的方式。