국보

최근 국립 박물관의 대전시실이 여러 차례 도난을 당해, 전시 중인 보물들의 안전을 모두가 걱정하고 있다. 박물관은 전시실을 지키기 위해 경비원을 추가로 고용해 유물들을 감시하게 하려 한다. 이때 전시실 전체가 안전하도록 만드는 데 필요한 최소 인원의 추가 경비원을 고용하고자 한다.

대전시실은 $R \times C$ 칸으로 이루어진 격자이다. 일부 칸에는 이미 박물관의 경비원이 서 있고, 나머지 칸에는 각각 어떤 종류의 유물(조각상, 조형물 등)이 놓여 있다. 유물은 새로 고용한 경비원으로 교체할 수 있지만, 경비원은 유물이 그대로 놓여 있는 칸에는 설 수 없으며, 유물을 단순히 치워 칸을 비워 둘 수도 없다. 즉 유물이 놓인 각 칸에 대해, 유물을 그대로 두거나 고용한 경비원으로 교체하는 두 가지 선택만 가능하다.

각 유물에는 핵심 지점들이 정해져 있다. 이는 그 유물을 전시실에 계속 두려면 반드시 경비원이 서 있어야 하는 칸들이다. 한 경비원이 여러 유물의 핵심 지점인 칸에 서 있으면, 그 유물들을 한꺼번에 감시할 수 있다. 임의의 유물의 핵심 지점은 항상 그 유물을 둘러싼 12개 칸의 부분집합이며, 아래 그림처럼 1번부터 12번까지 번호가 매겨져 있다(X는 유물 자신을 나타내고, 각 숫자는 그 번호의 핵심 지점을 나타낸다):

 .  2  .  3  .
 1  .  9  .  4
 . 12  X 10  .
 8  . 11  .  5
 .  7  .  6  .

유물의 종류는 음이 아닌 정수로 표현한다. 가장 낮은 자리 비트를 $1$번 비트로 셀 때, 이 정수의 $i$번째 비트가 $1$이라는 것은 $i$번 핵심 지점이 그 유물의 핵심 지점이라는 뜻이다. 예를 들어 종류가 $595$($2$진수로 $1001010011$)인 유물의 핵심 지점은 $\{1, 2, 5, 7, 10\}$이다. 유물의 핵심 지점이 격자 밖에 있으면, 그 지점은 자동으로 안전한 것으로 본다.

대전시실의 배치가 주어질 때, 남아 있는 모든 유물이 안전하도록 만드는 데 필요한 추가 경비원의 최소 인원을 구하여라.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 전시실의 크기를 나타내는 두 정수 $R$, $C$($1 \le R, C \le 50$)가 적힌 줄로 시작한다. 이어지는 $R$개의 줄에는 각각 한 개 이상의 공백으로 구분된 $C$개의 정수가 있다. $i$번째 줄의 $j$번째 정수는, 칸 $(i, j)$에 이미 박물관 경비원이 있으면 $-1$이고, 그렇지 않으면 그 칸에 놓인 유물의 종류를 나타내는 정수 $T$($0 \le T < 2^{12}$)이다.

입력의 끝은 두 개의 $0$이 적힌 줄로 표시되며, 이 종료 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다:

k. G

여기서 $k$는 테스트 케이스 번호($1$부터 시작)이고, $G$는 남아 있는 모든 유물이 안전하도록 만들기 위해 고용해야 하는 추가 경비원의 최소 인원이다.