Recently flood has vastly affected some regions of the country. So many people are helpless and suffering. They are in need of help. As you are very kind hearted person, you want to send yours helps to the affected areas.
You collected a 2D grid map of N x N size which shows the flood status of the country. The grid represents the following –
Any two flood affected grids are marked as same area if those share horizontal, vertical or diagonal grids. On the other hand, any two dry land grids marked as same area if those share horizontal and vertical grids. A shared grid of flood affected area and dry land area will be counted as different area.
A dry land will be marked as in danger zone of flood if it shares horizontal, vertical or diagonal grid with any flood affected area.
To send help you want to know the total flood affected areas and total areas that might be in danger zone of flood. You can assume to move through any types of grid in the map.
The input will start with a test case T <=10 .
Each test case will take the size N<=500 of the map followed by the N x N grid input.
For each test case print the case number, total flood affected areas and total areas in danger zone. Follow the output format in sample output.
| Input | Output |
|---|---|
2 3 ... .#* .*. 8 ..****.. ...###.. ....... ........ ........ ...##... ..***... ........ | Case 1: 1 2 Case 2: 2 2 |