스위치 배열

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

이 장치는 열린 상태와 닫힌 상태를 갖는 스위치 $s_1, s_2, \ldots, s_N$으로 이루어지고, 각 스위치의 상태는 0 또는 1이다. 따라서 장치의 상태는 0과 1로 이루어진 길이 $N$의 스위치 배열로 나타낸다.

다음 표는 스위치가 8개인 배열의 예다.

스위치 $N$개로 이루어진 배열에서 스위치를 작동시키는 규칙은 다음과 같다.

• 규칙 1) $s_N$은 아무 때나 토글해서 상태를 바꿀 수 있다.
• 규칙 2) $s_{i+1}$이 1이고 $s_{i+2}, s_{i+3}, \ldots, s_{N-1}, s_N$이 모두 0이면 $s_i$를 토글해서 상태를 바꿀 수 있다. 이 규칙은 $s_{i+2}, s_{i+3}, \ldots, s_{N-1}, s_N$에 해당하는 스위치가 아예 없을 때도 적용된다. 예를 들어 $s_{N-1}$은 $s_N$이 1이기만 하면 토글할 수 있다.
• 규칙 3) 한 번에 스위치 하나만 토글할 수 있다.

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

위 규칙에 따라 주어진 배열을 모두 0으로 바꾸는 최소 토글 횟수를 구하라.

아래 표는 배열 1111을 0000으로 바꾸는 가장 짧은 과정이다. 1111은 최소 10번의 토글로 0000이 된다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

이어서 각 테스트 케이스마다 비트열 $B$가 한 줄에 주어진다. $B$의 첫 비트가 $s_1$이고 마지막 비트가 $s_N$이다.

$B$의 길이는 $2 \le |B| \le 31$을 만족한다.

각 테스트 케이스마다 모든 스위치를 0으로 만드는 최소 토글 횟수를 한 줄에 출력한다.