问题背景

小杨有一个n×m的矩阵，仅包含0和1两种字符。矩阵的行从上到下编号依次为1,2,…,n，列从左到右编号依次为1,2,…,m。

小杨站在矩阵的左上角(1,1)，小杨只能向右或者向下移动，最终到达(n,m)时停止。

小杨想知道在经过的路径中，最多能够收集到多少个连续的1组成的连续段。

问题描述

给定一个n×m的矩阵，求小杨从左上角走到右下角的过程中，最多能收集到多少个连续的1组成的连续段。

格式

输入

第一行包含一个正整数t，代表测试用例组数。

接下来是t组测试用例。对于每组测试用例，一共n+1行。

• 第一行包含两个正整数n, m，含义如题面所示。
• 之后n行，每行包含一个长度为m且仅包含0和1两种字符的字符串。

输出

对于每组测试用例，输出一个整数，代表能收集到下小杨的最多连续段数量。

样例

输入数据 1

2
3 3
000
111
011
3 3
1?1
0?1
??0

输出数据 1

4
2

提示

对于第二组测试用例，将(1,1)或者(3,3)变成1均是最优解。

对于全部数据，保证：
1 ≤ t ≤ 10，1 ≤ n, m ≤ 500，1 ≤ Σ(n×m) ≤ 2.5×10^5