You are given a two-dimensional table (grid) A of N rows and M columns. Every cell contains a lowercase letter, one of 'a' - 'z'.

Let's call two cells of A adjacent, if they share a common side.

Let's call a set S of cells a connected region if the following three conditions are satisfied:

• S is connected, i.e. every pair of cells in S can be reached from each other by moving along a path of adjacent cells of S.
• All the letters written in the cells of S are the same.
• It's impossible to extend it, i.e. there are no more cells of A, that can be added to S so that the first two conditions still hold.

Every side of a cell is also called a side of the table. Let's call a side of the table inner, if it separates two adjacent cells. In a similar way, let's call a side of the table outer, if it lies on the border of the table.

For example, for a table of $N = 3$ rows and $M = 4$ columns, the blue sides are outer and the red sides are inner:

Let's say, that a connected region S is completely inside another connected region T, if there's a cycle path of adjacent cells of T, such that all the cells of S are inside the contour (shape), formed by the cycle path.

It's guaranteed that in the input no connected region is completely inside some other connected region.

Your task is to split A into a set of connected regions, separating each connected region from the others. You are allowed to pick some set of paths along inner sides of the table, that separate different connected regions, and make a cut along each of the paths.

• It's not allowed to cut an outer side.
• It's not allowed to cut some inner side more than once.
• It's not allowed to cut an inner side which doesn't separate different connected regions.
• Every inner side, that separates different connected regions, must be cut.

Please, read the sample explanation to understand the problem better.

It can be proved that it's always possible to split the table as described above. Can you find the minimum number of paths to do so?

Input format

The first line contains one integer T denoting the number of test cases in the input.

The first line of each test case description contains two integers N and M denoting the number of rows and the number of columns in A respectively.

Each of the next N lines contains a string of M lowercase letters, each denoting one row of the table A.

It's guaranteed that no connected region is completely inside some other connected region.

Output format

For each test case, in a separate line output the minimum number of paths to split the table the way described above.

Constraints

• $1 \le T \le 10$
• $1 \le N \cdot M \le 10^6$ (it's multiplication, not a comma)
• $N \le M$.

Subtasks