Shikar Kunal a.k.a BOT, visited admin building for getting permission for rooms for the event. He is disappointed by the administration and wants to get out of the building ASAP without being noticed by any professor. He is initially at cell (0,0) in the rectangular building of order RxC. He must reach the gate at (R-1,C-1) in order to get out. He can move from any cell, to any of it's 4 adjacent cells (North, East, West and South). If BOT 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

BOT somehow manages to get the map of the building.
If admin_map[x1][y1] == admin_map[x2][y2] then BOT can move from (x1,y1) to (x2,y2) without being noticed by any professor.
If admin_map[x1][y1] != admin_map[x2][y2], then BOT can move from (x1,y1) to (x2,y2) after interacting with a professor.

Given the map of the admin building, find the minimum number of professors BOT have to interact with to get out of the building.

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 building followed by R strings representing the map of the rectangular building.

Output:

For each test case find the minimum number of professors BOT must interact in order to escape the building.

Input Constraints:

1 <= t <= 10

2 <= R <= 1000

2 <= C <= 1000

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

Problem Setter

Aadersh Agarwal