描述

国家博物馆的大厅最近被抢劫了几次。现在，每个人都在担心展出的宝藏的安全性。为了帮助保护大厅的安全，博物馆与一家私人保安公司签订了合同，提供额外的警卫留在大厅并照看古代文物。博物馆希望雇用最少的额外警卫，以确保大厅的安全。

大厅表示为 R * C 单元的二维网格。一些牢房已经被博物馆的警卫占据。所有剩余的牢房都被不同类型的文物（雕像、雕塑......等）可以由新雇佣的警卫代替。对于每个文物，大厅中很少有其他单元格被确定为文物的关键点，具体取决于文物价值、保存其中的保险库类型以及少数其他因素。换句话说，如果这件神器要留在大厅里，那么它的所有关键点都必须有守卫站在上面。站在多个神器关键位置的守卫可以密切关注它们。然而，守卫不能站在包含文物的牢房中（相反，你可以移除文物，让守卫留在那里）。此外，您不能移除工件并留下空闲空间（您只能用新雇佣的警卫替换工件）。

通过调查大厅中的所有文物，您发现任何文物的关键点（用⊙标记）总是 12 个相邻单元格的子集，如下图所示。

因此，只有当上图中的临界点编号 i 是该伪影的临界点时，才能将项目的类型指定为非负整数，其中第 i 位为 1。例如，可以如下图所示显示类型 595 （二进制1001010011） 的工件。请注意，位是从右到左编号的（最右边的位是位号 1。如果工件的关键点位于霍尔网格之外，则认为它是安全的。

您将获得大厅的布局，并要求您找到要雇用的额外守卫的最低数量，以便保护所有剩余的文物。

输入

您的程序将在一个或多个测试用例上进行测试。每个测试用例都使用 R+1 行指定。第一行指定两个整数 （1 ≤ R，C ≤ 50），它们是博物馆大厅的尺寸。接下来的 R 行包含由一个或多个空格分隔的 C 整数。如果单元格 （i， j） 已经包含博物馆的一名守卫，则第 i 行的第 j 个整数为 -1，否则它包含一个整数 （0 ≤ T < 212） 表示该单元格中工件的类型。

输入文件的最后一行有两个零。

输出

对于每个测试用例，打印以下行：

k. G

其中 k 是测试用例编号（从 1 开始），G 是要雇用的额外守卫的最小数量，以便保护所有剩余的工件。

输入数据 1

1 3
512 -1 2048
2 3
512 2560 2048
512 2560 2048
0 0

输出数据 1

1. 0
2. 2

提示

该图显示了第二个测试用例的解决方案，其中中间的两个工件被守卫替换。