##### Bear and Row 01

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 ≤ 10
^{5}(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

Input:4 10100 1100001 000000000111 001110100011010Output:8 10 0 48

### 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.

### Solution

I have scored 25 points on this. Subtask #2 and #3 are getting TLE.Approach: Used regex to check if the string condition is met or not. If not, then I have run loop to check condition to swap "(strArr[j]=='1' && strArr[j+1]=='0')". If above condition is met, then I have found out next zero index with which the 1 can be swapped. Then I am swapping the integers and string count in a variable. Above all conditions are running in while loop which checks for regex (if the final condition is met.Feel free to discuss better approach, or to get approach I have used.Solutionpackage aprilChallenge2017; import java.util.Scanner; public class BearAndRow01 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); scan.nextLine(); for (int i = 0; i < t; i++) { String str = scan.nextLine(); if (str.matches("(0*)(1*)") || str.matches("(0*)") || str.matches("(1*)")) System.out.println("0"); else { char strArr[] = str.toCharArray(); int xx = 0; int moveCount = 0; while (!String.copyValueOf(strArr).matches("(0*)(1*)")) { int flag = 0; for (int j = 0; j < str.length() - 1; j++) { int oneIndex = -1; if (strArr[j] == '1' && strArr[j + 1] == '0') { oneIndex = j; int zeroIndex = j; int stepCount = 0; while (j < str.length()) { if ((strArr[j] == '0' && j == str.length() - 1) || (strArr[j] == '0' && strArr[j + 1] == '1')) { zeroIndex = j; flag = 1; break; } j++; stepCount++; } moveCount = moveCount + (stepCount + 1); strArr[zeroIndex] = '1'; strArr[oneIndex] = '0'; } if (flag == 1) break; } // for closes } // while closes System.out.println(moveCount); } } } }