Đầu Xuân năm mới, thầy Lữ tặng các bạn tham gia contest "Khai Xuân 2024" này một vài chuỗi lộc để lấy may mắn cho năm mới. Với chuỗi lộc này, các bạn cần phải thực hiện một vài thao tác biến đổi để nhận được phần quà từ thầy Lữ.

Chuỗi lộc chỉ bao gồm hai loại kí tự ~0~ và ~1~. Các bạn có thể thực hiện các thao tác xóa kí tự ~0~ trên chuỗi lộc, để nhận được quà từ thầy Lữ chuỗi lộc của bạn phải là chuỗi chứa ít nhất một kí tự ~1~ và các kí tự ~1~ trên chuỗi này phải đứng cạnh nhau.

Với mỗi chuỗi lộc mà thầy Lữ cho bạn, bạn hãy cho biết cần thực hiện ít nhất bao nhiêu thao tác xóa kí tự ~0~ để có thể đem chuỗi lộc này đổi quà từ thầy Lữ nhé. Nếu không có cách biến đổi nào để nhận được quà từ thầy Lữ bạn hay in ra ~-1~.

Input

Dòng đầu tiên chứa số nguyên ~T~ (~1 \leq T \leq 1000~) là số chuỗi lộc mà thầy Lữ cho bạn.

~T~ dòng tiếp theo, mỗi dòng sẽ chứa một chuỗi lộc ~S~ gồm ~N~ kí tự (~1 \leq N \leq 100~).

Output

Với mỗi chuỗi lộc, bạn hãy cho biết cần ít nhất bao nhiêu thao tác để có thể nhận được quà từ thầy Lữ.

Sample Input

3
010011
0
1111000

Sample Output

2
-1
0

SubTask

• SubTask 1: ~50\%~ số test với ~1 \leq N \leq 10~ và ~1 \leq T \leq 50~.
• SubTask 2: ~50\%~ số test còn lại, không có ràng buộc gì thêm.