#include <bits/stdc++.h>
using namespace std;

template <class res_t>
struct dinic {
    struct edge {
        int to;
        res_t flow, capacity;

        edge(int t = 0, res_t f = res_t(), res_t c = res_t()) {
            to = t, flow = f, capacity = c;
        }
    };

    void add_edge(int from, int to, int capacity) {
        edges.emplace_back(to, 0, capacity);
        graph[from].push_back((int) edges.size() - 1);

        edges.emplace_back(from, capacity, capacity);
        graph[to].push_back((int) edges.size() - 1);
    }

    bool bfs() {
        queue<int> que;
        fill(level.begin(), level.end(), -1);

        que.push(src), level[src] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();

            for (int i : graph[u]) {
                const edge& e = edges[i];
                if (level[e.to] == -1 && e.flow < e.capacity) {
                    level[e.to] = level[u] + 1;
                    que.push(e.to);
                }
            }
        }

        return level[dst] != -1;
    }

    res_t dfs(int u, res_t flow) {
        if (u == dst || flow == 0) {
            return flow;
        }

        res_t sum = 0;

        for (int &_ = current[u]; _ < (int) graph[u].size(); _++) {
            const int i = graph[u][_];
            edge &e = edges[i], &r = edges[i ^ 1];
            
            if (level[e.to] == level[u] + 1 && e.flow < e.capacity) {
                res_t used = dfs(e.to, min(flow - sum, e.capacity - e.flow));

                if (used != 0) {
                    e.flow += used, r.flow -= used;
                    sum += used;

                    if (sum == flow) {
                        break;
                    }
                }
            }
        }

        return sum;
    }

    res_t max_flow(int src, int dst) {
        this->src = src, this->dst = dst;

        res_t result = 0;
        
        while (bfs()) {
            fill(current.begin(), current.end(), 0);
            result += dfs(src, INFI);
        }

        return result;
    }

    dinic(int n) : tot(n), INFI(numeric_limits<res_t>().max()) {
        graph.assign(n, vector<int>());
        level.assign(n, -1);
        current.assign(n, 0);
    }

    const int tot;
    const res_t INFI;

    int src, dst;
    vector<edge> edges;
    vector<vector<int>> graph;
    vector<int> level, current;
};


int main(int argc, char **argv) {
    cin.sync_with_stdio(false), cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        dinic<int> flow(n * n * 2);

        vector<string> s(n);

        for (int i = 0; i < n; i++) {
            cin >> s[i];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                flow.add_edge(i * n + j, i * n + j + n * n, ((i == 0 && (j == 0)) || (i == n - 1 && j == n - 1)) + 1);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == '#') {
                    continue;
                }
                if (i + 1 < n && s[i + 1][j] != '#') {
                    flow.add_edge(i * n + j + n * n, (i + 1) * n + j, 1);
                }
                if (j + 1 < n && s[i][j + 1] != '#') {
                    flow.add_edge(i * n + j + n * n, i * n + j + 1, 1);
                }
            }
        }

        cout << flow.max_flow(0, 2 * n * n - 1) << "\n";
    }
}