## KATHTHI - KATHTHI

no tags

Kathiresan is initially locked at cell (0, 0) in a highly guarded rectangular prison of order R x C. He must reach the gate at (R-1, C-1) in order to escape from the prison. Kathiresan can move from any cell, to any of its 4 adjacent cells (North, East, West and South). If Kathiresan is currently at (x1, y1), then he can move to (x2, y2) if and only if abs(x2-x1)+abs(y2-y1) == 1 and 0 <= x2 < R and 0 <= y2 < C

Kathiresan somehow manages to get the map of the prison

If map[x1][y1] == map[x2][y2] then Kathiresan can move from (x1, y1) to (x2, y2) without killing any guards.

If map[x1][y1] != map[x2][y2] then Kathiresan can move from (x1, y1) to (x2, y2) by killing a guard.

Given the map of the prison, find the minimum number of guards Kathiresan must kill in order to escape from the prison.

### Input

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of two integers R and C representing the order of the rectangular prison followed by R strings representing the map of the rectangular prison.

### Output

For each test case find the minimum number of guards Kathiresan must kill in order to escape from the prison.

### Constraints

1 <= t <= 10

2 <= R <= 1000

2 <= C <= 1000

'a' <= map[i][j] <= 'z'

### Sample

```Input:
4
2 2
aa
aa
2 3
abc
def
6 6
akaccc
aaacfc
amdfcc
aokhdd
zyxwdp
zyxwdd
5 5
abbbc
abacc
aaacc
aefci
cdgdd

Output:
0
3
2
2
```