서기 20XX년, GTPC 연구소에서 인공지능 바이러스를 발견했다.

바이러스는 2진 코드의 일부 구간 값들이 0은 1로, 1은 0으로 바뀌는 변이를 통해 진화한다.

변이가 진행되는 규칙은 다음과 같다.

- 변이는 한 번에 한 구간만 일어난다.

- 아무 위치나 1개의 비트만 변이하거나, 오른쪽부터 C개의 비트가 한꺼번에 변이할 수 있다.

- 모든 2진 코드가 1이 되면 더 이상 변이가 일어나지 않는다.

예를 들어, 바이러스의 2진 코드 값이 110111000 이었다면, 다음과 같이 2번의 변이를 거쳐 111111111로 바뀌고 변이가 멈출 수 있다.

어떤 바이러스의 2진 코드 값이 주어질 때, 그 2진 코드 값이 모두 1로 바뀔 때까지 필요한 최소 변이 횟수를 출력해보자.

어떤 바이러스의 n비트 2진 코드 값이 한 줄로 입력된다.

[1 <= n <= 100,000] 

모든 2진 코드가 1로 바뀔 때까지 필요한 최소 변이 횟수를 출력한다.