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 begins with a single positive integer () on a line which indicates the number of the cases. Each test case will start with 2 integers () and () on a line. is the number of rows and is the number of columns of the grid. Then lines follows with characters each. Each character is either 0 or 1. 1 means a cell containing warehouse body and 0 means a blank cell.
For each test case, the output must contain the case number and the total number of guards required like sample output.
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 |