COUNTISL - How many Islands

no tags 

You are given a simple map of an archipelago. Can you determine how many islands it shows?

The map consists of grid squares with characters, where '#' indicates land and '.' indicates water. Two land squares belong to the same island if they are neighbouring grid squares, which means their x coordinates and y coordinates differ by at most 1.

Input

The first line of the input contains a number T ≤ 20 which indicates the number of test cases to follow.

Each test case starts with a line containing two numbers n and m (1 ≤ n,m ≤ 200), the number of rows and the number of columns of the grid, respectively. The following n lines contain m characters each and describe the map to be processed. You may assume that the map contains only characters '#' and '.', and that the border of the map consists only of water (character '.').

Output

For each test case print in a line the number of islands shown on the corresponding map in the input.

Example

Input:
2
1 1
.
6 4
....
..#.
.#..
....
.##.
....

Output:
0
2

hide comments
saketag007: 2018-09-18 22:41:12

Nice problem , AC in one go , 0.01s

learnerfirst: 2015-08-15 21:20:12

Getting NZEC. Java Code works on my system until the size 194*194, throws stackflowerror for anything above that. Is there any SUCCESSFUL submission in JAVA for this problem?

uptoyou: 2015-07-04 10:09:21

dfs :))

innovolt: 2014-04-11 22:01:03

1 more dfs applic.

Harsh Thakar: 2011-10-16 07:41:21

Getting WA. Some more test cases please


Added by:Adrian Kuegel
Date:2007-01-29
Time limit:3.087s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET