# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Putting Guards

Shetu is playing a popular game called “Putting Guards”. In this game there are various types of rectangular warehouses. The player has to calculate the minimum number of guards required to protect those. To protect those warehouses, each corner should have a guard. Shared corners should be covered by one guard. The whole space of the game is a 2D grid. The following figures explains some shapes of warehouses and necessary guards for them.

#### Input

Input begins with a single positive integer **T (T < 30)** on a line which indicates the number of the cases. Each test case will start with 2 integers **R (1≤ R ≤ 20)** and **C (1 ≤ C ≤ 20)** on a line. **R** is the number of rows and **C** is the number of columns of the grid. Then **R** lines follows with **C** characters each. Each character is either **0** or **1**. **1** means a cell containing warehouse body and **0** means a blank cell.

#### Output

For each test case, the output must contain the case number and the total number of guards required like sample output.

#### Samples

Input | Output |
---|---|

2 4 6 000000 000000 000011 000011 8 14 00000000000000 00000011000000 00000011000000 00011111111000 00011111111000 00000011000000 00000011000000 00000000000000 | Case 1: 4 Case 2: 12 |

Login to submit