在螞蟻的世界中，有一個很受歡迎的螞蟻購物中心，購物中心是個 $R\times{C}$ 的網格分布，每個格子可能有一家店，而購物中心是動態的，也就是說位於 $(r, c)$ 的店可能會移動，可以移動到 $(r, c - 1)$ 或者是 $(r, c + 1)$，如果該位置是空的才能移動，且不能移動到網格外。
蟻后想要參觀購物中心，蟻后會只會垂直移動，也就是選定一個 column 後，會從 $(r, c)$ 移動到 $(r + 1, c)$，蟻后只會從第一行 (row) $(1, c)$ 開始，最後移動到 $(R, c)$，購物中心的老闆為了招待蟻后要規劃一條沒有任何障礙物 (店家) 的路徑 $(1, c), (2, c), \ldots{}, (R, c)$。盡可能使最少店家移動最少次，老闆雇用你來解決這個問題。
Input
輸入第一行會有一個整數 $T$ ($T\leq{50}$)，表示有多少測資組。
每組測資會有兩個整數 $R, C$ ($2\leq{R}\leq{50}, 1\leq{C}\leq{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