깜빡이는 형광등

n개의 전등이 일렬로 놓여 있고, 각 전등에는 자기만의 버튼이 있다. 어떤 전등의 버튼을 누르면 그 전등의 상태가 바뀐다. 켜져 있으면 꺼지고, 꺼져 있으면 켜진다. 전등은 1초 단위의 타임스텝마다 변한다. 버튼은 아무 때나 누를 수 있지만, 누른 효과는 다음 타임스텝에야 나타난다. 각 타임스텝 직전에 버튼을 최대 하나 누를 수 있다(아무것도 누르지 않아도 된다).

버튼을 누르면 그 전등뿐 아니라 그 뒤에 있는 모든 전등에 영향을 준다. 구체적으로, k번째 타임스텝 직전에 i번째 버튼을 누르면, (i + m)번째 전등이 (k + m)번째 타임스텝에 상태가 바뀐다(i + m ≤ n). 예를 들어 19번째 타임스텝 직전에 5번 버튼을 누르면, 19번째 타임스텝에는 5번 전등이, 20번째 타임스텝에는 6번 전등이, 21번째 타임스텝에는 7번 전등이 상태가 바뀌는 식이다. 어떤 버튼을 눌러 그 효과가 앞선 버튼 입력 때문에 전등이 바뀌어야 할 시각과 같은 시각에 나타나면, 두 효과는 서로 상쇄된다. 이후의 상태 변화도 마찬가지로 상쇄된다.

전등이 세 개 있고 처음에는 모두 꺼져 있다고 하자. 첫 번째 타임스텝 직전에 첫 번째 버튼을 누르면 3초 동안 다음과 같이 된다.

이번에는 첫 번째 타임스텝 직전에 첫 번째 버튼을 누르고, 첫 번째와 두 번째 타임스텝 사이에 두 번째 버튼을 누른다고 하자. 이 버튼 입력이 전파를 상쇄해서 다음과 같이 된다(전파가 더 나아가지 않는다는 점에 주목하자).

이번에는 첫 번째 타임스텝 직전에 첫 번째 버튼을 누르고, 첫 번째와 두 번째 타임스텝 사이에 세 번째 버튼을 누른다고 하자. 두 번째 타임스텝에 세 전등이 모두 켜진다(세 번째 타임스텝에는 아니다).

모든 전등을 켜고 싶다. 모든 전등이 켜진 모습을 볼 수 있는 가장 이른 시각은 언제인가? 시각 t에 모든 전등이 켜져 있지만 이 전파 때문에 t + 1에는 켜져 있지 않더라도, 답은 여전히 t이다.

각 입력은 하나의 테스트 케이스로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다. 각 테스트 케이스는 하나의 문자열 S(1 ≤ |S| ≤ 16)로 이루어진다. S는 문자 1과 0만 포함하며, 1은 그 전등이 처음에 켜져 있음을, 0은 처음에 꺼져 있음을 나타낸다. 첫 번째 문자가 1번 전등이고, 그다음이 2번 전등인 식이다.

모든 전등이 켜지는 가장 이른 시각을 정수 하나로 출력한다.