问题描述

新格尔公司的天才程序员菜哭武刚刚在市中心买下了一块地，他想自己盖一个别墅，但是由于地点实在是太好，他在修房子的时候必须满足一些要求，在某些地方只能使用某些特定的材料。比如说，从他家门口到马路上的路，只能在设计好的 $N$ 个 $1 \times M$ 的瓷砖序列中选择，他可以决定选择哪些瓷砖，但是不能改变相对顺序，不能旋转或者翻转，并且不能重复选择。每块瓷砖由黑色和白色的小块构成，可以看成一个 $01$ 字符串，$0$ 表示白色的小块，$1$ 表示黑色的小块。在走的时候，菜哭武只喜欢走黑色的区域，并且每次他可以移动到前、左、右相邻的三个格子（不要问我为什么他不可以往其他的方向走，菜哭武就喜欢这样）。他现在的想法是让自己的门尽可能的离马路远一些，由于他家的门还没确定放在哪里，所以只需要连出来一条尽量长的瓷砖序列，选用的瓷砖数量越多越好，并且菜哭武可以按照上述喜好从马路走到别墅。天才程序员菜哭武自然是知道怎么算的，但是他实在是太忙了，所以想让你帮他来算一下。

输入格式

第一行一个整数 $T$，表示有 $T$ 组测试数据。（$T \leq 10$）

每组测试数据，第一行包含两个整数 $N, M$。（$N \leq 500$，$2 \leq M \leq 365$）

$N$ 表示可以选择模块数量，$M$ 表示每个模块的长度。

然后有 $N$ 行，每行是一个长度为 $M$ 的 $01$ 串。

输出格式

对于每组数据，第一行输出 Case #x:（$x$ 编号从 $1$ 开始）。

然后第二行输出一个整数，表示最长的路有多长。

样例输入

2
3 3
000
001
100
4 5
00001
11101
10111
10000

样例输出

Case #1:
1
Case #2:
3

提示

样例解释：

第一组数据中，第 $2$、$3$ 个任意一个均可。

第二组数据中，第 $1$、$2$、$3$ 个或者第 $2$、$3$、$4$ 个两种方案。因为每次走的时候只能选择前、左、右三个方向，所以全部选择的方案是不可以的。