Звонок часового механизма

Кролики — это маленькие млекопитающие из семейства зайцевых отряда зайцеобразных. Так говорит Википедия. Правильно. Следовательно, они не скучны, ведь они все оригинальные и хорошо организованы. Кролики на нашей ферме живут в охраняемых загонах, границы которых украшены замысловатыми цветочными орнаментами. В загонах растут множество очаровательных оранжевых кустиков моркови. Кролики быстро размножаются (это норма, каждый год рождаются полчища кроликов), и наши наставники стремятся легко отслеживать их в загонах.

Загончики организованы упорядоченно — они образуют один прямой ряд. В начале первого сезона размножения некоторые загончики могут быть пустыми. В конце каждого сезона размножения проводится хорошо скоординированная пересадка кроликов. Пересадка регулируется простой формулой, которая зависит от одного положительного целого параметра $k$, который можно выбрать произвольно для каждого сезона. Пересадка осуществляется параллельно для всех загонов. В каждом загончике примерно половина кроликов убирается и пересаживается на $k$ загонов вниз по ряду. Не имеет значения, занят ли целевой загон или нет.

Если загон находится слишком близко к концу ряда (меньше чем на $k$ загонов вниз по ряду), то все кролики остаются в загоне и никуда не пересаживаются. Любой загон может вместить неограниченное количество кроликов, и в любом непустом загоне всегда достаточно кроликов для успешного размножения.

Дано начальное расположение загонов, показывающее, какие из них заняты кроликами, а какие пусты в начале первого сезона размножения. Определите минимальное количество пересадок, необходимых для того, чтобы все загончики были заселены кроликами.

Входные данные

Заданая строка длиной $b(1\le b\le 40)$ символов, где каждый символ представляет один загон и является либо $0$ (пустой загон), либо $1$ (занятый загон). Первый символ соответствует первому загону в ряду.

Выходные данные

Выведите минимальное количество пересадок, необходимых для того, чтобы все загончики были заселены кроликами. Если заселить все загончики невозможно при любом количестве пересадок, выведите $-1$.

Примеры