시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 478 231 190 48.346%

문제

새로운 잠금 장치가 개발되었다.

이 장치는 열리거나 닫힌 상태를 갖는 여러 스위치(s1, s,.., si-1, si)들로 이루어져 있으며, 각각의 스위치는 0 또는 1의 상태를 갖는다. 따라서, 각 장치는 0과 1로 이루어진 스위치 배열로 나타낼 수 있다.

다음 표는 8개의 스위치를 가진 스위치 배열의 예제이다.

switch s1 s2 s3 s4 s5 s6 s7 s8
state 0 1 1 0 1 1 0 0

N개의 스위치를 가진 배열의 각 스위치를 작동시키는 규칙은 다음과 같다.

  • 규칙 1) SN은 아무 때나 토글하여 상태를 바꿀 수 있다.
  • 규칙 2) Si+1 = 1이며 Si+2, Si+3, ..., SN-1, SN은 모두 0일 때, Si를 토글하여 상태를 바꿀 수 있다. 이 규칙은 스위치 Si+2, Si+3, ..., SN-1, SN가 없을 때도 적용된다. 예를 들어, SN-1은 SN이 1이기만 하면 토글할 수 있다.
  • 규칙 3) 한 번에 하나의 스위치만 토글할 수 있다.

모든 스위치의 상태가 0일 때 이 장치는 열린다.

위의 규칙에 따라 배열을 모두 0으로 바꾸는 최소 토글 횟수를 구하는 것이 당신의 과제이다.

아래의 표는 배열 '1111' 을 '0000' 으로 바꾸는 최소 횟수의 연산을 나타낸 것이다. '1111' 의 경우, 최소 10번의 연산으로 배열을 '0000' 으로 만들 수 있다.

operation s1 s2 s3 s4
0 1 1 1 1
1 1 1 0 1
2 1 1 0 0
3 0 1 0 0
4 0 1 0 1
5 0 1 1 1
6 0 1 1 0
7 0 0 1 0
8 0 0 1 1
9 0 0 0 1
10 0 0 0 0

입력

입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 비트스트링 B가 한 줄에 주어지며, B의 첫 비트가 S1, 마지막 비트가 SN이다.

B의 길이는 2 ≤ |B| ≤ 31 을 만족한다.

출력

각 테스트 케이스마다 한 줄에 모든 스위치를 0으로 만들기 위한 최소의 연산 횟수를 출력한다.

예제 입력

5
1111
11111
1010101010
000
000000010

예제 출력

10
21
819
0
3

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2014 J번