{"code":"findminmex","name":"Tìm MIN MEX","description":"Cho một xâu nhị phân $s$ chỉ gồm các kí tự $0$ và $1$\r\n + 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$.\r\n ++ 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$\r\n ++ 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$\r\n\r\nBây giờ, An đố bạn một bài toán như sau:\r\n\r\nCho 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.\r\n\r\n+ 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$\r\n+ 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$\r\n+ 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$\r\n\r\n#### Input\r\n - Dòng đầu tiên chứa số nguyên dương $t(1\\le t\\le 100)$ - Thể hiện số testcase \r\n - $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$\r\n\r\n#### Output\r\n- Ứng với mỗi testcase, hãy in kết quả ra màn hình.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        3\r\n        01\r\n        1111\r\n        01100\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        1\r\n        0\r\n        2\r\n        ```","points":777.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}