ABC 431

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define fi first
#define se second
#define y1 noip200

using namespace std;

const int N = 3e5 + 50, p = 1e9 + 7;
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int n, m;
int dist[4 * N];

void init() {

}

int id(int x, int y, int z) {
	return z * n * m + (x - 1) * m + y;
}

// 0: up
// 1: down
// 2: left
// 3: right

void solve() {
	scanf("%d%d", &n, &m);
	vector <vector <char>> a(n + 15, vector <char> (m + 15, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char ch = ' ';
			while (ch < 'A') scanf("%c", &ch);
			a[i][j] = ch;
		}
	}
	vector <pair <int, int>> e[4 * n * m + 50];
// vector <pair <int, int>> e[4 * N]; // ??????
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) {
			if (i > 1) e[id(i, j, 0)].push_back({id(i - 1, j, 0), a[i][j] != 'A'});
			if (j > 1) e[id(i, j, 0)].push_back({id(i, j - 1, 2), a[i][j] != 'B'});
			if (j < m) e[id(i, j, 0)].push_back({id(i, j + 1, 3), a[i][j] != 'C'});
			
			if (i < n) e[id(i, j, 1)].push_back({id(i + 1, j, 1), a[i][j] != 'A'});
			if (j < m) e[id(i, j, 1)].push_back({id(i, j + 1, 3), a[i][j] != 'B'});
			if (j > 1) e[id(i, j, 1)].push_back({id(i, j - 1, 2), a[i][j] != 'C'});
			
			if (j > 1) e[id(i, j, 2)].push_back({id(i, j - 1, 2), a[i][j] != 'A'});
			if (i > 1) e[id(i, j, 2)].push_back({id(i - 1, j, 0), a[i][j] != 'B'});
			if (i < n) e[id(i, j, 2)].push_back({id(i + 1, j, 1), a[i][j] != 'C'});
			
			if (j < m) e[id(i, j, 3)].push_back({id(i, j + 1, 3), a[i][j] != 'A'});
			if (i < n) e[id(i, j, 3)].push_back({id(i + 1, j, 1), a[i][j] != 'B'});
			if (i > 1) e[id(i, j, 3)].push_back({id(i - 1, j, 0), a[i][j] != 'C'});
		}
	e[id(n, m, 3)].push_back({0, a[n][m] != 'A'});
	e[id(n, m, 1)].push_back({0, a[n][m] != 'B'});
	deque <int> q;
	for (int i = 0; i <= 4 * n * m + 505; i++) 
		dist[i] = 1 << 30;
	dist[id(1, 1, 3)] = 0;
	q.push_back(id(1, 1, 3));
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		if (dist[u] >= 1 << 30) break;
		if (!u) break;
		for (auto [v, w] : e[u]) 
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				if (w) q.push_back(v);
				else q.push_front(v);
			}
	}
	printf("%d\n", dist[0]);
}

int main() {
	init();
	int t = 1;
	scanf("%d", &t);
	while (t--) solve();
	return 0;
}