Ankur and Jyoti are two friends who always keep fighting over which one is smarter. To resolve their issue their third friend Sidharth designs a new card game and decides that whoever wins the game will be declared as the smartest of the two once and for all. The game consists of a sequence of cards, some of which are placed face up and some are face down. Each participant is given the sequence and they have to flip the cards one at a time in a manner such that finally all cards are face down. The rule is whoever finishes the game earliest wins the game. The only problem is their mischievous friend Anuja, every time the participant flip some card, she also flips 1 card on the right side and 1 card on the left side of the card flipped by the participant. Help them in finding the minimum time to arrange the cards face down.

Each flip of card by the participant adds 1 ms time.

Input

First line specifies the number of test cases T.

Next T lines gives a string consisting of 1’s and 0’s, 1 representing face up and 0 representing face down.

Output

For each test case Print one line for the minimum time (in ms) required to convert all the given cards as face down, Print -1 if there is no way that you can face down all the cards at the same time.

Note: when 1^st card is flipped Anuja will flip only its right card since its left doesn’t exist, similarly for the last card in sequence.

Constraints

T ≤ 10

1 ≤ Length of string ≤ 15

Example

Input:
2
100101111111111
000000000000111

Output:
7
1