Cho \(T\) xâu nhị phân \(S\) chỉ chứa toàn các kí tự \(0\) và \(1\). Một xâu nhị phân được gọi là đẹp khi xâu chứa ít nhất một kí tự \(1\) và các kí tự \(1\) phải đứng cạnh nhau. Bạn có thể sử dụng phép xóa kí tự \(0\). Hãy cho biết với mỗi xâu cần ít nhất bao nhiêu phép xóa để xâu trở thành xâu nhị phân đẹp. Nếu không có cách nào thì in ra \(-1\).

INPUT FORMAT

Dòng đầu tiên gồm một số nguyên \(T\ (1\leq T\leq 1000)\).

\(T\) dòng tiếp theo, mỗi dòng chứa \(1\) xâu \(S\ (1\leq |S|\leq 100)\).

OUTPUT FORMAT

Gồm \(T\) dòng, ứng với mỗi dòng là kết quả cần tìm.

Ví dụ:

Input

3
010011
0
1111000

Output

2
-1
0

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House