An có chuỗi nhị phân \(S\) (chỉ gồm các số 0 hoặc 1). Bạn ấy thử xóa một vài kí tự 0 trong \(S\) để các kí tự 1 trong S tạo thành một đoạn liên tiếp dài nhất.

• Chuỗi S là: 010011 An sẽ xóa đi các ký tự 0 ở vị trí thứ 3 và thứ 4 trong chuỗi S, như vậy chuỗi kết quả là 0111 và các chữ số 1 lúc này tạo thanh một đoạn liên tiếp dài nhất.
• Chuỗi S là 111111100 thì An không cần xoá kí tự 0 nào cả.

Yêu cầu:

Em hãy viết chương trình tính số lượng tối thiểu các kí tự \(0\) cần xoá để so sánh kết quả với An xem bạn ấy làm có đúng không nhé.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên T cho biết số bộ dữ liệu cần kiểm tra.
• T dòng sau, mỗi dòng chứa một chuỗi nhị phân S khác rỗng.

Kết quả:

• T dòng, mỗi dòng ghi một số là số lượng tối thiểu các chữ 0 cần xóa khỏi chuỗi S. Nếu không tạo được đoạn 1 liên tiếp thì in ra -1.

Ràng buộc:

• 20% số test ứng với 20% số điểm của bài thỏa mãn: T ≤ 10; 1 ≤ độ dài S ≤ 10
• 80% số test ứng với 80% số điểm của bài thỏa mãn: T ≤ 1000; 1 ≤ độ dài S ≤ 1000

Ví dụ: