11920 - 0 s, 1 s and ? Marks

給定一個只有0, 1, ? 這三種字元的字串，介由把 ? 以 0 或 1 代換之後，使字串內最大長度的群組最小化，定義連續的 0 或連續的 1 為同一群組，例如下列字串：
0 1 1 ? 0 1 0 ? ? ?
將問號 ? 以0或1取代後得到：
0 1 1 0 0 1 0 1 0 0
分類不同群組得到(0) (1 1) (0 0) (1) (0) (1) (0 0)，群組長度分別為：1, 2, 2, 1, 1, 1, 2，所以用上述的方式取代掉'?'之後可發現最大的群組長度為2。事實上，所有共2^4=16種排列組合中，最大的群組長度不會小於2。

Input 

輸入的第一列為整數T(T <= 5000)表示測試資料的長度，接下的有T列字串，每一個字串僅包含0, 1, ?三種字元，字串長度介於[1, 1000]之間。

Output

請輸出每組測試資料字串的最小化最大群組長度可能的值。

Sample Input 

4
011?010???
???
000111
00000000000000

Sample Output 

Case 1: 2
Case 2: 1
Case 3: 3
Case 4: 14

---

原文出處