You are given a string (s) of length (n) consisting of (\mathtt{0}) and/or (\mathtt{1}). In one operation, you can select a non-empty subsequence (t) from (s) such that any two adjacent characters in (t) are different. Then, you flip each character of (t) ((\mathtt{0}) becomes (\mathtt{1}) and (\mathtt{1}) becomes (\mathtt{0})). For example, if (s=\mathtt{\underline{0}0\underline{101}}) and (t=s_1s_3s_4s_5=\mathtt{0101}), after the operation, (s) becomes (\mathtt{\underline{1}0\underline{010}}). Calculate the minimum number of operations required to change all characters in (s) to (\mathtt{0}). Recall that for a string (s = s_1s_2\ldots s_n), any string (t=s_{i_1}s_{i_2}\ldots s_{i_k}) ((k\ge 1)) where (1\leq i_1 < i_2 < \ldots <i_k\leq n) is a subsequence of (s). The first line of input contains a single integer (t) ((1 \leq t \leq 10^4)) — the number of input test cases. The only line of each test case contains the string (s) ((1\le |s|\le 50)), where (|s|) represents the length of (s). For each test case, output the minimum number of operations required to change all characters in (s) to (\mathtt{0}). In the first test case, you can flip (s_1). Then (s) becomes (\mathtt{0}), so the answer is (1). In the fourth test case, you can perform the following three operations in order: Flip (s_1s_2s_3s_4s_5). Then (s) becomes (\mathtt{\underline{01010}}). Flip (s_2s_3s_4). Then (s) becomes (\mathtt{0\underline{010}0}). Flip (s_3). Then (s) becomes (\mathtt{00\underline{0}00}). It can be shown that you can not change all characters in (s) to (\mathtt{0}) in less than three operations, so the answer is (3).