Cho một binary string (xâu nhị phân) \(s\) chỉ bao gồm các kí tự \('0'\) và \('1'\).

Một phép biến đổi được định nghĩa như sau:

• Chọn một kí tự trong \(string\) \(s\) và đảo kí tự đó, tức là \('0'\) đảo thành \('1'\), còn \('1'\) đảo thành \('0'\).

Một string được gọi là \(good\) nếu như nó không chứa bất kì đoạn con (không cần liên tục) nào bằng \("010"\) hoặc \("101"\). Ví dụ, \(s="1001"\) chứa \("101"\) là đoạn con nên \("1001"\) \(không\) \(phải\) là \(good\) \(string\), trong khi \(s="1000"\) là \(good\) \(string\).

Một đoạn con không liên tục của một string s là một string thu được bằng cách xóa đi một số kí tự (có thể không xóa) của \(s\).

Yêu cầu : Hãy cho biết số lần biến đổi tối thiểu để làm cho \(string\) \(s\) trở thành \(good\) \(string\).

Input

• Dòng đầu in ra một số nguyên là \(T (1 \leq T \leq 100)\) - số lượng bộ test.
• \(T\) dòng tiếp theo mỗi dòng chứa một binary \(string\) \(s\) \((1 \leq s.size() \leq 1000)\).

Output

• Mỗi bộ test in trên một dòng là một số nguyên - số lần biến đổi tối thiểu để làm cho string s trở thành good.

Example

3
001
110
01011001 

0
0
3