#1613 Islands

71  1 s   128 MB  

Description

 

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.

 

Input

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

Each test case starts with two positive integers rc, 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 '#'.

 

 

 

Output

 

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