在螞蟻的世界中，有一個很受歡迎的螞蟻購物中心，購物中心是個 R×C 的網格分布，每個格子可能有一家店，而購物中心是動態的，也就是說位於 (r,c) 的店可能會移動，可以移動到 (r,c−1) 或者是 (r,c+1)，如果該位置是空的才能移動，且不能移動到網格外。
蟻后想要參觀購物中心，蟻后會只會垂直移動，也就是選定一個 column 後，會從 (r,c) 移動到 (r+1,c)，蟻后只會從第一行 (row) (1,c) 開始，最後移動到 (R,c)，購物中心的老闆為了招待蟻后要規劃一條沒有任何障礙物 (店家) 的路徑 (1,c),(2,c),…,(R,c)。盡可能使最少店家移動最少次，老闆雇用你來解決這個問題。
Input
輸入第一行會有一個整數 T (T≤50)，表示有多少測資組。
每組測資會有兩個整數 R,C (2≤R≤50,1≤C≤50)，接下來會有 R 行，每行上會有 C 個字元，每個字元只會由 0 或 1 構成，第 i 行第 j 個字元表示 (i,j)，如果 (i,j)=1 表示該位置有店家，反之沒有。
Output
對於每組測資，輸出最少的移動次數，如果沒辦法找到一條路徑則輸出 -1。
Sample Input
3
2 4
1010
0101
3 3
111
111
111
3 5
01111
11110
11011
Output for Sample Input
Case 1: 1
Case 2: -1
Case 3: 4