Migrated from Lutece 1086 邱老师降临小行星

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

人赢邱老师和任何男生比，都是不虚的。有一天，邱老师带妹子(们)来到了一个$N$行$M$列平面的小行星。对于每一个着陆地点，邱老师总喜欢带着妹子这样走：假设着陆地点为$(r_0, c_0)$，那么他们下一步只能选择相邻格点，向四周走，即$(r_0–1, c_0)$, $(r_0 + 1, c_0)$, $(r_0, c_0–1)$或$(r_0, c_0 + 1)$。之后的路程必须严格按照右转-前进-左转-前进-右转......的道路前行。但是由于邱老师很心疼妹子，所以崎岖的山脉不可以到达。当不能前进时必须要原路返回。如下图。

问，邱老师在哪里着陆可以游历这颗星球最多的土地，输出可能访问到的最多的格点数。

Input

第一行一个整数$T$, $0< T\le 20$，表示输入数据的组数。
对于每组数据，第一行有两个整数$N$和$M$，分别表示行数和列数，$0< N,M\le 1000$
下面$N$行，每行$M$个字符($0$或$1$)。
$1$代表可到达的地方，$0$代表山脉(不可到达的地方)。

Output

对于每一组数据，输出一个整数后换行，表示选择某点着陆后，可能访问到的最多的格点数。

Samples

2
4 3
111
111
111
111
3 3
111
101
111

10
4

Resources

2015 UESTC Training for Search Algorithm & String