LONGCS

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;

int n;

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;
    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }
    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

vector<int> suffix_array_construction(string s) {
    s += "$";
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}


vector<int> lcp_construction(string const& s, vector<int> const& p) {
    int n = s.size();
    vector<int> r(3*n, 0);
    for (int i = 0; i < n; i++)
        r[p[i]] = i;
    int k = 0;
    vector<int> lcp(n-1, 0);
    for (int i = 0; i < n; i++) {
        if (r[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[r[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k])
            k++;
        lcp[r[i]] = k;
        if (k)
            k--;
    }
    return lcp;
}

int m[N][24];
int lg[N];

int getMin(int u, int v) {
    int k = lg[v - u + 1];
    return min(m[u][k], m[v - (1 << k) + 1][k]);
}

void RMQ_process(vector <int> &a) {
    int n = a.size();
    for(int i = 2; i <= n; i++)
		lg[i] = lg[i / 2] + 1;
    for (int i = 0; i < n; i++) m[i][0] = a[i];

    for (int k = 1; (1 << k) <= n; k++)
        for (int i = 0; i + (1 << k) - 1 < n; i++)
            m[i][k] = min(m[i][k - 1], m[i + (1 << (k - 1))][k - 1]);
}


int getAns(vector <int> &t) {
    int ans = 1e9+8;
    for (int i = 0; i < t.size(); i++) {
        if (t[i] == -1)
            return 0;
    }
    for (int i = 1; i < t.size(); i++) {
        int u = min(t[i-1], t[i]);
        int v = max(t[i-1], t[i]);
        ans = min(ans, getMin(u, v-1));
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int k;
        cin >> k;
        string s = "";
        vector <int> t(k, 0);getchar();
        for (int i = 0; i < k; i++) {
            t[i] = s.size();
            string tmp = "";
            cin >> tmp;
            s += tmp;
            if (i != k-1) s += char(i);
        }
        vector <int> p = suffix_array_construction(s);
        vector <int> lcp = lcp_construction(s, p);
        RMQ_process(lcp);
        int res = 0;
        vector <int> id(k, -1);
        int cnt = 0;
        for (int x: p) {
            int i = upper_bound(t.begin(), t.end(), x) - t.begin() - 1;
            id[i] = cnt;
            res = max(res, getAns(id));
            cnt++;
        }
      	if (k == 1) {
            res = s.size();
        }
        cout << res << endl;
    }
}