Archiwum zadań programistycznych WWSI

Grześ w przerwach pomiędzy rozwiązywaniem zadań usilnie poszukuje nowych form rozrywki. Wszelkie gry planszowe oraz gra "kamień, papier, nożyce" już dawno znudziły się naszemu bohaterowi i postanowił stworzyć coś zupełnie nowatorskiego. Swój najnowszy pomysł nazwał "redukcją liczby".

Gra polega na tym, że z pewnej liczby zapisanej w postaci binarnej w każdym ruchu usunąć można dowolny spójny podciąg zer lub jedynek, o ile jego długość jest większa od 1. Jeżeli w wyniku usunięcia podciągu powstała luka, Grześ scala ze sobą pozostałe ciągi. Gra kończy się w momencie gdy nie ma możliwości usunięcia kolejnego podciągu albo wszystkie cyfry zostały już usunięte.

Nasz bohater chciałby wiedzieć jaka jest minimalna liczba ruchów niezbędnych do całkowitego zredukowania liczby, o ile jest to w ogóle możliwe. Pomóż Grzesiowi i napisz program, który dla każdej wczytanej liczby binarnej wyznaczy minimalną ilość ruchów potrzebnych do całkowitego jej zredukowania albo wypisze - w przypadku, kiedy jest to niemożliwe.

Wejście

W pierwszej linii wejścia znajduje jedna liczba całkowita n (1 ≤ n ≤ 100) określająca ilość liczb do zredukowania. W kolejnych n liniach znajdują liczby do zredukowania w zapisie binarnym (mogą zawierać wiodące zera). Długość każdej z liczb nie przekracza 25 cyfr.

Wyjście

Na wyjściu dla każdej liczby wypisz minimalną ilość ruchów potrzebną do jej całkowitego zredukowania albo - jeżeli jest to niemożliwe.

Przykład

Wejście

2
01110
0101

Wyjście

2
-