Let us interpret this problem as a graph theory problem.

For each edge in the grid, define two vertices corresponding to the two directions crossing over the edge. (Figure below)

The placements of the mirror in a cell can be considered as directed edges between the vertices like the following:

Here, changing the placement of the mirror in a cell corresponds to altering the vertices that the directed edges point at. In other words, we can consider that we can move to the originally pointed vertex with cost \(0\), and to the other vertices with cost \(1\).

(For a type-A cell, the red edges can be traversed with cost \(0\), and the blue edges can be traversed with cost \(1\).)

This allows us to solve the problem with 01-BFS (Breadth-First Search).

When implementing, it is a good idea to assign a number to each of the four directions, and compute \(\mathrm{dp}[x][y][d]\) defined as the minimum cost required to reach the vertex pointed from cell \((x,y)\) in direction \(d\).

In the sample code below, we use the following techniques:

• Assign to directions down, right, up, and left, numbers \(0, 1, 2, 3\)
• Assign the numbers \(0, 1, 2, 3\) to the directions down, right, up, and left. Let \((x,y)\) be the current cell, \(dir\) be the direction of entering cell \((x,y)\), and \(ndir\) be the direction of exiting cell \((x,y)\). Then:
  • Moves such that \(\mathrm{dir}\oplus \mathrm{ndir}=2\) are disallowed.
  • If \(S[x][y]\) is A: moves with \(\mathrm{dir}\oplus \mathrm{ndir}=0\) costs \(0\), and the others cost \(1\).
  • If \(S[x][y]\) is B: moves with \(\mathrm{dir}\oplus \mathrm{ndir}=1\) costs \(0\), and the others cost \(1\).
  • If \(S[x][y]\) is C: moves with \(\mathrm{dir}\oplus \mathrm{ndir}=3\) costs \(0\), and the others cost \(1\).

from collections import deque

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
d = {"A": 0, "B": 1, "C": 3}


def solve():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]
    dp = [[[1 << 30] * 4 for _ in range(w)] for _ in range(h)]

    dq = deque()
    dq.append((0, 0, -1, 1))
    while dq:
        c, pre_x, pre_y, dir = dq.popleft()
        x, y = pre_x + dx[dir], pre_y + dy[dir]
        if not (0 <= x < h and 0 <= y < w):
            continue
        for ndir in range(4):
            if dir ^ ndir == 2:
                continue
            if dir ^ ndir == d[s[x][y]]:
                # cost : 0
                if c < dp[x][y][ndir]:
                    dp[x][y][ndir] = c
                    dq.appendleft((c, x, y, ndir))
            else:
                # cost : 1
                if c + 1 < dp[x][y][ndir]:
                    dp[x][y][ndir] = c + 1
                    dq.append((c + 1, x, y, ndir))

    print(dp[h - 1][w - 1][1])


for _ in range(int(input())):
    solve()