71 1 s 128 MB

The king is trying to find new ways to generate revenue, and he is currently exploring tourism as one potential avenue. The **kingdom** is a group of islands, and the amount of revenue that can be generated depends on the combined total length of beaches on all the islands.

You are given a String[] **kingdom** consisting of '.' or '#' characters. '#' represents a land mass, whereas '.' represents water. **kingdom**[i][j] represents a regular-hexagon shaped area with each side of unit length. Since the cells are hexagonal in shape, the odd-numbered rows (0-based) are 'shifted' towards the right. A beach is a segment which has water on one side, and land on the other.

An example String[] and the corresponding image are given below to illustrate. The beaches are marked in red.

`{"..#.##", ".##.#.", "#.#..."} `

Print the combined total length of beaches on all the islands.

The first line of the input gives the number of test cases, **T** (1 <= **T** <= 200).

Each test case starts with two positive integers **r**, **c**, representing number of rows and columns of **kingdom**, respectively. **R** and **c** is between 1 and 50, inclusive.

For next **r** lines, length **c** string representing r-th line of **kingdom** is given. Each character of the string will be either '.' or '#'.

For each test case, print the number as explained in the problem statement, in one line.

## Sample Input | ## Sample Output |
---|---|

4 1 8 .#...#.. 3 6 ..#.## .##.#. #.#... 2 10 #...#..... ##..#...#. 4 6 ....#. .#.... ..#..# ####.. | 4 19 15 24 |