Mirror 是 Steam 上一款难以描述但很有趣的游戏。不过，本题讨论的是现实中的镜子。
Rikka 有一个 $n \times m$ 的半透明网格，每个网格方块的边长均为 1。她可以从网格外部向网格内发射光线，光线从某个方块边界的中点射入，且垂直于该边界。在网格内经过一系列运动后，光线会从另一个方块边界的中点射出。我们可以很容易地计算出光线在网格内的路径长度。
网格内放置有若干面镜子，每面镜子的长度均为 $\sqrt{2}$。放置镜子有两种方式：连接方块的左下角和右上角，或者连接方块的左上角和右下角。如果光线射到镜子上，它会遵循物理定律发生反射并改变方向。
以下是一个例子。
该网格大小为 $3 \times 4$，内部放置了四面镜子。如果 Rikka 从方块 $(3, 3)$ 的底边中点向网格内发射光线，光线最终会经过所有四面镜子，并从方块 $(1, 1)$ 的顶边中点射出。光线的路径长度为 7。
显然，Rikka 有 $2(n + m)$ 种发射光线的方式。Rikka 将网格的“价值”定义为所有这些方式中光线路径长度的总和。
现在，Rikka 有一个内部没有任何镜子的 $n \times m$ 空网格。她想在网格的某些方块中放置若干面镜子，以最小化网格的价值。每个方块最多只能放置一面镜子。不幸的是，经过研究，Rikka 发现某些方块的镜子插槽是损坏的，因此她完全无法在这些方块中放置镜子。
这是一个令人沮丧的发现，所以 Rikka 放弃了自己计算价值，希望你能帮她得到答案。请找出 $n \times m + 1$ 个数字：分别表示放置 0 面镜子、最多 1 面镜子、最多 2 面镜子、……、最多 $n \times m$ 面镜子时的最小网格价值。
输入格式
第一行包含一个整数 $t$ ($1 \le t \le 100$)，表示测试用例的数量。
对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 5, 1 \le m \le 7$)。
接下来 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串。如果第 $i$ 行的第 $j$ 个字符为“1”，则表示可以在方块 $(i, j)$ 中放置镜子；如果为“0”，则表示不能放置。
保证 $n = 5$ 且 $m = 7$ 的测试用例不超过 2 个。
输出格式
对于每个测试用例，输出一行，包含 $n \times m + 1$ 个整数。第 $i$ 个数字表示放置最多 $i - 1$ 面镜子时的最小网格价值。
样例
输入 1
2 3 3 101 011 101 4 4 1111 1111 1111 1111
输出 1
36 36 36 36 20 20 20 20 20 20 64 64 64 64 40 40 40 40 32 32 32 32 24 24 24 24 24