리카와 거울

Mirror는 Steam에 있는 설명하기 어렵지만 재미있는 게임이다. 하지만 이 문제는 실제 거울에 관한 문제다.

리카는 $n \times m$ 크기의 반투명 격자를 가지고 있다. 격자 각 칸의 한 변 길이는 정확히 $1$이다. 리카는 격자 바깥에서 어떤 칸 변의 가운데 점을 향해, 그 변에 수직으로 빛을 쏠 수 있다. 빛은 격자 안에서 진행한 뒤, 다른 칸 변의 가운데 점으로 격자를 빠져나간다. 격자 안에서 빛이 지나는 경로의 길이는 쉽게 계산할 수 있다.

격자 안에는 여러 개의 거울이 있고, 거울의 길이는 정확히 $\sqrt{2}$다. 거울은 칸의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점을 잇는 자리에 놓거나, 왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점을 잇는 자리에 놓는다. 빛이 거울에 닿으면 물리 법칙에 따라 반사되어 진행 방향이 바뀐다.

예를 들어 보자. 격자의 크기는 $3 \times 4$이고, 격자 안에 거울이 4개 있다. 리카가 칸 $(3, 3)$의 아래쪽 변 가운데 점으로 빛을 쏘면, 빛은 결국 거울 4개를 모두 거쳐 칸 $(1, 1)$의 위쪽 변 가운데 점으로 나온다. 이때 빛의 경로 길이는 $7$이다.

빛을 쏘는 방법은 $2 (n + m)$가지다. 리카는 이 모든 방법에서 나온 빛 경로 길이의 합을 격자의 값으로 정의한다.

이제 리카에게는 거울이 하나도 없는 빈 $n \times m$ 격자가 있다. 리카는 거울 몇 개를 칸에 놓아 격자의 값을 최소로 만들려고 한다. 각 칸에는 거울을 최대 1개까지만 놓을 수 있다. 안타깝게도 일부 칸은 거울 슬롯이 고장 나 있어서 거울을 전혀 놓을 수 없다. 리카는 값을 직접 계산하는 일을 포기하고 답을 구해 달라고 부탁한다. 거울을 0개, 최대 1개, 최대 2개, ..., 최대 $n \times m$개 놓았을 때 격자 값의 최솟값을 차례로 구하라. 즉 $n \times m + 1$개의 수를 구한다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \leq t \leq 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$, $m$ ($1 \leq n \leq 5$, $1 \leq m \leq 7$)이 주어진다.

이어서 $n$개의 줄이 주어지며, 각 줄은 길이 $m$의 이진 문자열이다. $i$번째 줄의 $j$번째 문자가 "1"이면 칸 $(i, j)$에 거울을 놓을 수 있고, "0"이면 놓을 수 없다.

$n = 5$이고 $m = 7$인 테스트 케이스는 최대 2개임이 보장된다.

각 테스트 케이스마다 $n \times m + 1$개의 정수를 한 줄에 출력한다. $i$번째 수는 거울을 최대 $i - 1$개 놓았을 때 격자 값의 최솟값이다.