Count Tribal Villages

You are given a grid representing a kingdom. Each cell in the grid can be one of three characters:

• T — representing a tribal village cell.
• . — representing an empty cell.
• # — representing an obstacle (barrier).

A tribal village is defined as a connected group of T cells which are adjacent vertically or horizontally (not diagonally). Your task is to count the number of distinct tribal villages in the grid.

The connection can be mathematically expressed as: two cells u and v belong to the same component if there exists a sequence of cells \(u = c_0, c_1, \dots, c_k = v\) such that for each \(i\), \(|c_i - c_{i+1}| = 1\) in either the row or column direction.

inputFormat

The first line of input contains two integers n and m — the number of rows and columns in the grid, respectively. (1 ≤ n, m ≤ 1000)

The following n lines each contain a string of length m composed solely of the characters T, ., and #.

outputFormat

Output a single integer representing the number of distinct tribal villages in the grid.

4 4
T..T
.#.#
T##T
..T.

5