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

• Ta định nghĩa giá trị \(MEX(s)\) là số nguyên \(z\) nhỏ nhất thoả mãn: \(z\) thuộc tập \(\{0,1,2\}\) và \(z\) không thuộc xâu \(s\).
  ++ Ví dụ 1: Giả sử ta có xâu \(s=0110\), thì \(MEX(s)=2\), vì các số \(0\) và \(1\) đã xuất hiện trong xâu \(s\)
  ++ Ví dụ 2: Giả sử ta có xâu \(s=11\), thì \(MEX(s)=0\), vì mặc dù \(0\) và \(2\) cùng không xuất hiện trong xâu \(s\) nhưng \(0<2\) nên \(MEX(s)=0\)

Bây giờ, An đố bạn một bài toán như sau:

Cho một xâu nhị phân \(s\), nhiệm vụ của bạn là hãy đặt các vách ngăn giữa các kí tự của xâu \(s\), và các vách ngăn này chia xâu \(s\) thành các xâu con sao cho tổng MEX của các xâu con này là nhỏ nhất có thể, và in giá trị nhỏ nhất này ra màn hình.

• Ví dụ 1: Cho xâu \(s=01\). Thì chúng ta ngăn xâu \(s\) thành như sau: \(|0|1|\). Và tổng giá trị MEX các xâu con là: \(MEX(0) + MEX(1) = 1+0 = 1\)
• Ví dụ 2: Cho xâu \(s=1111\). Thì chúng ta ngăn xâu \(s\) thành như sau: \(|1111|\). Và tổng giá trị MEX của các xâu con là: \(MEX(1111)=0\)
• Ví dụ 3: Cho xâu \(s=01100\). Thì chúng ta ngăn xâu \(s\) thành như sau: \(|0|11|00|\). Và tổng giá trị MEX của các xâu con là: \(MEX(0) + MEX(11) + MEX(00) = 1+0+1=2\) hoặc chúng ta có cách ngăn khác là: \(|01100|\), thì cũng thu được kết quả là: \(MEX(01100)=2\)

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 100)\) - Thể hiện số testcase
• \(t\) dòng tiếp theo, mỗi dòng chứa một xâu s, biết rằng \(1\le |s|\le 10^4\), trong đó \(|s|\) là độ dài của xâu \(s\)

Output

• Ứng với mỗi testcase, hãy in kết quả ra màn hình.

Example

3
01
1111
01100

1
0
2