Untitled

#include <bits/stdc++.h>

using namespace std;

void File() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MON
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("errors.txt", "w", stderr);
#else
#endif
}

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char di[] = {'D', 'U', 'R', 'L'};

int main() {
    File();
    int tt;
    cin >> tt;
    for (int tc = 0; tc < tt; ++tc) {
        int n, m;
        cin >> n >> m;
        char a[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> a[i][j];
            }
        }
        vector<vector<int>> lvl(n, vector<int>(m, 1e8));
        deque<pair<int, int>> q;
        lvl[0][0] = 0;
        q.push_back({0, 0});
        while (!q.empty()) {
            int i = q.front().first, j = q.front().second;
            q.pop_front();
            for (int k = 0; k < 4; ++k) {
                int ni = i + dx[k], nj = j + dy[k];
                if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                    int dist = lvl[i][j];
                    if (a[i][j] != a[ni][nj]) dist++;
                    if (dist < lvl[ni][nj]) {
                        lvl[ni][nj] = dist;
                        if (a[i][j] != a[ni][nj])
                            q.push_back({ni, nj});
                        else
                            q.push_front({ni, nj});
                    }
                }
            }
        }
        cout << lvl[n - 1][m - 1] << "\n";
    }

    return 0;
}