Given a string consisting of 0, 1 and ? only, change all the ? to 0/1, so that the size of the largest group is minimized. A group is a substring that contains either all zeros or all ones. Consider the following example: 011?010??? We can replace the question marks (?) to get 0110010100 The groups are (0) (1 1) (0 0) (1) (0) (1) (0 0) and the corresponding sizes are 1, 2, 2, 1, 1, 1, 2. That means the above replacement would give us a maximum group size of 2. In fact, of all the 24 possible replacements, we won’t get any maximum group size that is smaller than 2. Input The first line of input is an integer T (T ≤ 5000) that indicates the number of test cases. Each case is a line consisting of a string that contains 0, 1 and ? only. The length of the string will be in the range [1,1000]. Output For each case, output the case number first followed by the size of the minimized largest group. Sample Input 4 011?010??? ??? 000111 00000000000000 Sample Output Case 1: 2 Case 2: 1 Case 3: 3 Case 4: 14