#define NDEBUG
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define range(i, n) for (int i = 0; i < n; i++)

using namespace std;
constexpr int maxn = 400;

template <size_t N> struct my_bitset {
    const int v_size;
    int n;
    ull v[(N+63)/64];
    my_bitset(int n = N) : v_size((n+63)/64), n(n) {
        assert(n<=N);
        assert(n>=0);
        range(i, v_size) v[i] = 0;
    }
    my_bitset(string s, int n = N) : v_size((n+63)/64), n(n) {
        assert(n<=N);
        assert(n>=0);
        assert(s.length() == n);
        range(i, v_size) v[i] = 0;
        range(i, v_size) range(j, 64) if (s[i*64 + j] == '1') v[i] |= (1LL << (63 - j));
    }
    void flip() {
        range(i, v_size) v[i] = ~v[i];
    }
    bool read(int index) {
        assert(index >= 0);
        assert(index < n);
        int cell = index / 64;
        int shift = index % 64;
        return (v[cell] & (1LL << (63 - shift)));
    }
    void set(int index, bool value) {
        assert(index >= 0);
        assert(index < n);
        int cell = index / 64;
        int shift = index % 64;
        if (value) v[cell] |= (1LL << (63 - shift));
        else v[cell] &= ~(1LL << (63 - shift));
    }
    void operator= (my_bitset<N> other) {
        range(i, v_size) v[i] = other.v[i];
    }
    void operator= (string s) {
        assert(s.length() == n);
        range(i, v_size) v[i] = 0;
        range(i, v_size) range(j, 64) if (s[i*64 + j] == '1') v[i] |= (1LL << (63 - j));
    }
    my_bitset<N> operator& (my_bitset<N> other) {
        my_bitset<N> out(this);
        range(i, v_size) out[i] &= other[i];
        return out;
    }
    void operator&= (my_bitset<N> other) {
        range(i, v_size) v[i] &= other.v[i];
    }
    my_bitset<N> operator| (my_bitset<N> other) {
        my_bitset<N> out(this);
        range(i, v_size) out[i] |= other[i];
        return out;
    }
    void operator|= (my_bitset<N> other) {
        range(i, v_size) v[i] |= other.v[i];
    }
    int first_one() {
        int index = 0;
        for (; index < v_size; index++) if (v[index] != 0) break;
        if (index == v_size) return -1;
        int leading_zeros = __builtin_clzll(v[index]);
        int out = leading_zeros + index * 64;
        if (out >= n) return -1;
        assert(out >= 0);
        return out;
    }
    int pop_first_one() {
        int index = 0;
        for (; index < v_size; index++) if (v[index] != 0) break;
        if (index == v_size) return -1;
        int leading_zeros = __builtin_clzll(v[index]);
        int out = leading_zeros + index * 64;
        if (out >= n) return -1;
        assert(out >= 0);
        v[index] &= ~(1LL << (63 - leading_zeros));
        return out;
    }
    string display() {
        string s = "";
        range(i, N) s += (read(i) ? "1" : "0");
        cout << s << "\n";
        return s;
    }
};

struct Node {
    my_bitset<maxn> canMoveTo;
    vector<int> dists;
    Node(int n) : dists(maxn), canMoveTo(n) {}
    void read_can_move_to() {
        string s;
        cin >> s;
        canMoveTo = s;
    }
};

struct Graph {
    vector<Node> v;
    int n;
    int tp_a = -1, tp_b = -1;
    Graph(int n) : v(n, n), n(n) {
        range(i, n) v[i].read_can_move_to();
        range(i, n) distances(i, false);
        int worst = 0;
        range(i, n) range(j, n) worst = max(worst, v[i].dists[j]);
        int best = worst;
        range(i, n) for (int j = i + 1; j < n; j++) {
            if (worst - best >= v[i].dists[j]) continue;
            tp_a = i;
            tp_b = j;
            int optimal = distances(i, true);
            int check = optimal;
            range(k, n) {
                int dist = min(v[k].dists[i], v[k].dists[j]);
                if (optimal + dist <= check) continue;
                check = max(check, distances(k, true));
            }
            best = min(best, check);
        }
        cout << best << "\n";
    }
    int distances(int from, bool with_tps) {
        int worst = 0;
        bool keep_checking_tps = with_tps;
        my_bitset<maxn> not_visited(n);
        not_visited.flip();
        not_visited.set(from, false);
        int curSteps = 0;
        queue<int> bfs;
        bfs.push(from);
        if (keep_checking_tps) {
            if (from == tp_a) {
                not_visited.set(tp_b, false);
                bfs.push(tp_b);
                keep_checking_tps = false;
            }
            else if (from == tp_b) {
                not_visited.set(tp_a, false);
                bfs.push(tp_a);
                keep_checking_tps = false;
            }
        }
        bfs.push(-1);
        while (true) {
            int top = bfs.front();
            bfs.pop();
            if (top == -1) {
                if (bfs.empty()) return curSteps;
                bfs.push(-1);
                curSteps++;
                continue;
            }
            else v[from].dists[top] = curSteps;
            my_bitset<maxn> visitable(not_visited);
            visitable &= v[top].canMoveTo;
            int next;
            while ((next = visitable.pop_first_one()) != -1) {
                if (!not_visited.read(next)) continue;
                not_visited.set(next, false);
                bfs.push(next);
                if (keep_checking_tps) {
                    if (next == tp_a && not_visited.read(tp_b)) {
                        not_visited.set(tp_b, false);
                        bfs.push(tp_b);
                        keep_checking_tps = false;
                    }
                    else if (next == tp_b && not_visited.read(tp_a)) {
                        not_visited.set(tp_a, false);
                        bfs.push(tp_a);
                        keep_checking_tps = false;
                    }
                }
            }
        }
    }
};

void solve() {
    int n;
    cin >> n;
    Graph g(n);
}

void test() {
    my_bitset<400> a;
    cout << a.read(2) << "\n";
    a.set(2, true);
    cout << a.read(2) << "\n";
    a.flip();
    cout << a.read(2) << "\n";
    cout << a.read(1) << "\n";
    a.set(1, false);
    cout << a.read(1) << "\n";
    a.flip();
    cout << a.pop_first_one() << "\n";
    cout << a.pop_first_one() << "\n";
    cout << a.pop_first_one() << "\n";
    a.flip();
    range(i, 399) a.pop_first_one();
    cout << a.first_one() << "\n";
    a.set(399, false);
    cout << a.pop_first_one() << "\n";

    exit(0);
}
void test2() {
    ull a = 3;
    cout << __builtin_clzll(a) << "\n";

    exit(0);
}
void test3() {
    string a = "10110", b = "01000";
    my_bitset<5> ab(a), bb(b);
    ab.display();
    bb.display();
    ab = b;
    ab.display();

    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) solve();
}