Description

Bella是一个拉丁舞者，当她在舞台上翩翩起舞时，观众会为她鼓掌。舞台是一个正n边形，每个边上都有一排观众，Bella站在舞台的正中央。将边按逆时针顺序从1到n标号。演出结束后谢幕时，当Bella将身子转向正朝第i条边的方向时，她能完整地看到若干条边上的观众（如下图所示，当Bella正朝AB这条边时，Bella可以完整看到AG、AB、BC三条边上的观众）。若舞台是一个正n边形，Bella正对着一条边时能完整看到的边的数量为(n-2)/4*2+1条。每一个时刻Bella都会转向任意一个方向，但一定是正朝着某条边的。如果某个时刻一整排的观众鼓掌了，并且Bella能完整地看到这些观众鼓掌，那么Bella就会增加1的快乐值。快乐值进入到下一个时刻会清零。

已知谢幕要进行 T 时刻， 每个时刻都会给出有哪些观众鼓掌有哪些没鼓掌，你需要对于每个时刻找到一个朝向使 Bella 在这个时刻的快乐值最大。

Input Format

输入 T+1 行，第一行两个正整数 n,T。

接下来 T 行，每行给出一个长度为 n 的 0/1 字符串表示每条边上的观众是否鼓掌。

Output Format

输出 T 行。对于每一个时刻，输出这个时刻 Bella 能达到的最大的快乐值。

7 10
1010010
1101101
0010010
1100100
1101001
1011010
0010101
1101010
0001010
0100100

2
3
1
2
3
2
2
2
2
1

Hint

对于 50%的数据，3≤n,T≤500。
对于 100%的数据，3≤n,T≤5000。