Ghét xâu con

Cho một xâu nhị phân $s$ (chỉ gồm các ký tự 0 và 1). Trong một thao tác, bạn chọn một vị trí trong xâu và lật ký tự tại vị trí đó (0 thành 1 hoặc 1 thành 0).

Một xâu được gọi là đẹp nếu nó không chứa xâu con (subsequence) 010 và cũng không chứa xâu con 101. Ở đây "xâu con" hiểu theo nghĩa subsequence: thu được bằng cách xoá đi một số (có thể là 0) ký tự, các ký tự còn lại giữ nguyên thứ tự.

Với mỗi test, hãy tính số thao tác ít nhất cần thực hiện để biến $s$ thành một xâu đẹp.

Có thể chứng minh rằng luôn tồn tại cách biến đổi.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số lượng test trong file.
• $t$ dòng tiếp theo, mỗi dòng chứa một xâu nhị phân $s$.

Dữ liệu ra

Với mỗi test, in ra trên một dòng số thao tác ít nhất cần thực hiện.

Ràng buộc

• $1\le t\le 100$
• $1\le |s|\le 1000$
• $s$ chỉ gồm các ký tự 0 và 1.

Ví dụ