Cho một chuỗi nhị phân \(s\). Hãy cắt \(s\) thành ít đoạn nhất sao cho sau khi cắt, các đoạn có thể nối lại với nhau (theo thứ tự nào đó) để tạo ra một chuỗi nhị phân đã được sắp xếp.

Lưu ý:

• Mỗi ký tự phải thuộc đúng một đoạn.
• Mỗi đoạn phải là một đoạn con liên tiếp của chuỗi ban đầu.
• Phải sử dụng tất cả các đoạn khi nối chúng lại với nhau.

Một chuỗi nhị phân là chuỗi chỉ gồm hai ký tự 0 và 1. Một chuỗi nhị phân đã được sắp xếp là chuỗi mà mọi ký tự 0 đều đứng trước mọi ký tự 1.

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(t\) (\(1 \leq t \leq 500\)) — số lượng bộ test.
• Dòng duy nhất của mỗi bộ test chứa một chuỗi \(s\) (\(1 \leq |s| \leq 500\)) bao gồm các ký tự 0 và 1, trong đó \(|s|\) biểu thị độ dài của chuỗi \(s\).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất — số lượng đoạn ít nhất cần thiết để có thể sắp xếp lại chuỗi thành một chuỗi nhị phân đã được sắp xếp.

Scoring

• Subtask \(1\) \((10\%)\): Chuỗi chỉ toàn 0 hoặc toàn 1.
• Subtask \(2\) \((20\%)\): Chuỗi đã được sắp xếp.
• Subtask \(3\) \((30\%)\): Chuỗi chỉ có đúng 2 khối liên tiếp (Ví dụ: 111000 hoặc 000111).
• Subtask \(4\) \((40\%)\): Không có ràng buộc gì thêm.

Example

6
11010
00000000
1
10
0001111
0110

3
1
1
2
1
2