github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: ROWSOLD
problem_name: 'Bear and Row 01'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYPY
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM chicken'
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: errichto
problem_tester: null
date_added: 3-04-2017
tags:
    - april17
    - errichto
    - greedy
editorial_url: 'https://discuss.codechef.com/problems/ROWSOLD'
time:
    view_start_date: 1492421400
    submit_start_date: 1492421400
    visible_start_date: 1492421400
    end_date: 1735669800
    current: 1497284104
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/APRIL17/mandarin/ROWSOLD.pdf), [Russian](http://www.codechef.com/download/translated/APRIL17/russian/ROWSOLD.pdf) and [Vietnamese](http://www.codechef.com/download/translated/APRIL17/vietnamese/ROWSOLD.pdf) as well.

Limak is a little polar bear. He is playing a video game and he needs your help.

There is a row with N cells, each either empty or occupied by a soldier, denoted by '0' and '1' respectively. The goal of the game is to move all soldiers to the right (they should occupy some number of rightmost cells).

The only possible command is choosing a soldier and telling him to move to the right as far as possible. Choosing a soldier takes 1 second, and a soldier moves with the speed of a cell per second. The soldier stops immediately if he is in the last cell of the row or the next cell is already occupied. Limak isn't allowed to choose a soldier that can't move at all (the chosen soldier must move at least one cell to the right).

Limak enjoys this game very much and wants to play as long as possible. In particular, he doesn't start a new command while the previously chosen soldier moves. Can you tell him, how many seconds he can play at most?

### Input

The first line of the input contains an integer **T** denoting the number of test cases. The description of **T** test cases follows.

The only line of each test case contains a string **S** describing the row with N cells. Each character is either '0' or '1', denoting an empty cell or a cell with a soldier respectively.

### Output

For each test case, output a single line containing one integer — the maximum possible number of seconds Limak will play the game.

### Constraints

- 1 ≤ **T** ≤ 5
- 1 ≤ N ≤ 105 (N denotes the length of the string **S**)

### Subtasks

- Subtask #1 (25 points): 1 ≤ N ≤ 10
- Subtask #2 (25 points): 1 ≤ N ≤ 2000
- Subtask #3 (50 points): Original constraints.

### Example

<pre><b>Input:</b>
4
10100
1100001
000000000111
001110100011010

<b>Output:</b>
8
10
0
48
</pre>### Explanation

**Test case 1.**The initial string is 10100. There are N = 5 cells. There is one soldier in the first cell, and one soldier in the third cell. The following scenario maximizes the total time:

- Limak chooses the soldier in the first cell. This soldier can move only one cell to the right. It takes 1 second to choose a soldier and 1 second for a soldier to move to the next cell (2 seconds in total). The string is 01100 now.
- Limak has only one choice. He must choose the soldier in the third cell because the other soldier can't move at all (the soldier in the second cell can't move to the right because the next cell is already occupied). Choosing a soldier takes 1 second. The chosen soldier moves from the third cell to the fifth cell, which takes 2 seconds. This operation takes 1 + 2 = 3 seconds in total. The string is 01001 now.
- Limak has only one choice again. Since the soldier in the last row can't move further to the right, the soldier in the second cell must be chosen. He will move 2 cells to the right. This operation takes 1 + 2 = 3 seconds in total. The string become 00011 and the game is over.

The total time is 2 + 3 + 3 = 8.

**Test case 2.**The initial string is 1100001. There is only one possible scenario:

- 1100001 is changed to 1000011 in 5 seconds (1 second to choose a soldier and 4 seconds for the soldier to move 4 cells to the right).
- 1000011 is changed to 0000111 in 5 seconds.

The total time is 5 + 5 = 10 seconds.

**Test case 3.**The game is over immediately because all soldiers occupy rightmost cells already. The answer is 0.