Counting Islands

You are given a 2D map represented as an M x N grid, where each cell is either L (land) or W (water). An island is defined as a group of connected lands (cells with L) that are adjacent horizontally or vertically. Your task is to count the number of distinct islands in the map.

The connectivity condition between cells is given by the four directions: up, down, left, and right.

Note: When counting islands, once a cell forming part of an island is visited, all adjacent cells in four directions are considered visited. This is analogous to the flood fill algorithm. The DFS (Depth First Search) technique is often used to solve similar problems.

The relation for grid cell traversal can be illustrated as:

\(dfs(x, y)\): if cell \((x,y)\) is land, mark it as visited and recursively visit its neighbors.

inputFormat

The input is given via standard input (stdin) with the following format:

1. The first line contains a single integer \(T\), representing the number of test cases.
2. For each test case, the first line contains two space-separated integers \(M\) and \(N\) where \(M\) is the number of rows and \(N\) is the number of columns in the grid.
3. This is followed by \(M\) lines, each containing a string of length \(N\). Each character in the string is either L (land) or W (water).

outputFormat

For each test case, output a single integer on a new line representing the number of distinct islands in the corresponding grid. The output should be written to standard output (stdout).

## sample

2
4 5
LLWWL
LWLWL
WWWLL
LLLLW
3 3
LLW
LWL
WLL

3
2

</p>