huyhau6a2 hiện đang có một chương trình tên là binary.cpp. Trong code của cậu có thực hiện các bước như sau:

• Bước 1: Nhập vào chương trình một xâu nhị phân $s$ (xâu nhị phân là xâu chỉ bao gồm các ký tự 0 và 1). Thực hiện bước 2.
• Bước 2: Kiểm tra xem trong xâu $s$ có xuất hiện đoạn ký tự 10 hay không, nếu có thì thực hiện bước 3, còn không thì kết thúc chương trình.
• Bước 3: Thay đồng loạt tất cả các đoạn ký tự 10 xuất hiện trong xâu $s$ thành 01. Quay lại bước 2.

Ví dụ: Với xâu $s=$1100 thì chương trình sẽ thực hiện như sau:

• Kiểm tra thấy có đoạn ký tự 10 xuất hiện, chuyển qua bước 3.
• Thay tất cả đoạn ký tự 10 thành 01. Xâu $s$ trở thành 1010. Quay lại bước 2.
• Kiểm tra thấy có đoạn ký tự 10 xuất hiện, chuyển qua bước 3.
• Thay tất cả đoạn ký tự 10 thành 01. Xâu $s$ trở thành 0101. Quay lại bước 2.
• Kiểm tra thấy có đoạn ký tự 10 xuất hiện, chuyển qua bước 3.
• Thay tất cả đoạn ký tự 10 thành 01. Xâu $s$ trở thành 0011. Quay lại bước 2.
• Kiểm tra thấy không có đoạn ký tự 10 xuất hiện, kết thúc chương trình.
  Vậy với xâu $s=$1010 thì chương trình sẽ thực hiện bước 3 hai lần.

Với chương trình mà huyhau6a2 viết, rõ ràng nó sẽ kết thúc sau một vài lần thực hiện bước 3, tức là nó không chạy vô hạn. Nhiệm vụ của bạn là xác định xem với xâu $s$ mà huyhau6a2 chuẩn bị nhập vào cần thực hiện bước 3 bao nhiêu lần.

Input

• Dòng đầu gồm một số nguyên dương $t$ là số testcase $(1\le t\le 10^5)$.
• Sau đó là $t$ dòng, mỗi dòng gồm một xâu $s$ là xâu mà huyhau6a2 sẽ nhập vào chương trình $(1\le |s|\le 2\times 10^5)$.
• Dữ liệu đảm bảo tổng độ dài của các xâu $s$ trong tất cả testcase không quá $2\times 10^5$.

Output

• Với mỗi testcase, in ra duy nhất một giá trị là số lần thực hiện bước 3 trong một dòng.

Sample

Sample Input 1

4
1100
00011
1011001
1011001110

Sample Output 1

3
0
4
6

Notes

• Testcase thứ nhất đã được giải thích ở phần statement.
• Trong testcase thứ ba, xâu $s$ sau các thao tác như sau: 1011001$\rightarrow$0110101$\rightarrow$0101011$\rightarrow$0010111$\rightarrow$0001111.
• Trong testcase thứ tư, xâu $s$ sau các thao tác như sau: 1011001110$\rightarrow$0110101101$\rightarrow$0101011011$\rightarrow$0010110111$\rightarrow$0001101111$\rightarrow$0001011111$\rightarrow$0000111111