longest common sub string

/*  TAHMID RAHMAN
    DAMIAN FOREVER
     MATH LOVER
    NEVER GIVE UP
*/
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define pb push_back
#define fi first
#define se second
#define in insert
#define mp make_pair
#define GCD(a,b) __gcd(a,b);
#define endl "\n"
#define FRU freopen("out.txt","w",stdout)
#define FRO freopen("in.txt","r",stdin)
#define INFLL 9223372036854775807
#define all(x) (x).begin(),(x).end()
#define MAXN   100001
#define ar array
#define lb lower_bound
#define ub upper_bound
#define minpq priority_queue<ll, vector<ll>, greater<ll>>
#define maxpq priority_queue<ll>
const int mxN=2e5;
const int MOD=1e9+7;
template<typename ForwardIterator, typename T>
ForwardIterator first_less_than (ForwardIterator first, ForwardIterator last, T value)
{auto it = std::lower_bound (first, last, value);
return (it == first ? last : --it);}
bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
    return (a.second < b.second);
}
#define debugxx(v) {for(auto x:v){cout<<x.fi<<" "<<x.se<<endl;}cout<<endl;}
#define debugx(v){for(auto y:v) {cout<<y<<" ";}cout<<endl;}
#define debug(x) cout<<#x<<" ";_print(x); cout<<endl;
typedef unsigned long long ull;
typedef long double lld;
void _print(ll t) {cout << t;}
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(lld t) {cout << t;}
void _print(double t) {cout << t;}
void _print(ull t) {cout << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.fi); cout << ","; _print(p.se); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
//Don't hesitate to ask me if you don't understand my code.......Happy coding,Tahmid...;

vector<ll> SortCyclicShifts(string s){
    int n=s.size();
    const int alphabet=256;
    vector<ll>Start(n),Freq(max(alphabet,n),0),EClass(n);
    for(int i=0;i<n;i++) Freq[s[i]]++;
    for(int i=1;i<alphabet;i++) Freq[i]+=Freq[i-1];
    for(int i=0;i<n;i++) Start[--Freq[s[i]]]=i;
    int Class=1;
    EClass[Start[0]]=0;
    for(int i=1;i<n;i++){
        if(s[Start[i]]!=s[Start[i-1]]) Class++;
        EClass[Start[i]]=Class-1;
    }
    for(int p=0;(1<<p)<n;p++){
        vector<ll> STemp(n),ECTemp(n);
        for(int i=0;i<n;i++){
            STemp[i]=Start[i]-(1<<p);
            if(STemp[i]<0) STemp[i]+=n;
        }
        fill(Freq.begin(),Freq.begin()+Class,0);
        for(int i=0;i<n;i++) Freq[EClass[STemp[i]]]++;
        for(int i=1;i<Class;i++) Freq[i]+=Freq[i-1];
        for(int i=n-1;i>=0;i--){
            Start[--Freq[EClass[STemp[i]]]]=STemp[i];
        }
        ECTemp[Start[0]]=0;
        Class=1;
        for(int i=1;i<n;i++){
            pair<ll,ll>prev,curr;
            prev={EClass[Start[i-1]],EClass[(Start[i-1]+(1<<p))%n]};
            curr={EClass[Start[i]],EClass[(Start[i]+(1<<p))%n]};
            if(curr!=prev) Class++;
            ECTemp[Start[i]]=Class-1;
        }
        for(int i=0;i<n;i++){
            EClass[Start[i]]=ECTemp[Start[i]];
        }
    }
    return Start;
}
vector<ll> BuildSuffixArray(string s){
    s+='$';
    vector<ll>ret=SortCyclicShifts(s);
    ret.erase(ret.begin());
    return ret;
}


 vector<ll> lcp(vector<ll>&sa,string &s)
{
    ll n=sa.size();
    vector<ll>ranks(n);
    ll h=0,i=0;
    s+='$';
    vector<ll>l(n,0);
    for(i=0;i<n;i++)
       ranks[sa[i]]=i;


    for(i=0;i<n;i++)
    {
        if(ranks[i]>0)
        {
            ll k=sa[ranks[i]-1];
            while(s[i+h]==s[k+h]){
                h++;
            }

            l[ranks[i]]=h;

            if(h)
               h--;
        }
    }

    return l;

}

ll lcp(ll a,ll b,vector<ll>&v)
{
    ll i=a+1;
    ll ans=v[i];

    for(i=a+1;i<=b;i++)
    {
        ans=min(ans,v[i]);
    }

    return ans;
}

int main()
{
    fastio;
    ll t;
    //t=1;
    cin>>t;
    while(t--)
    {
        ll n,i,j,k;
        cin>>n;

        map<ll,ll>m;
        string s1,s;
        for(i=0;i<n;i++)
        {
            cin>>s;
            s1+=s;
            s1+='0'+i;
        }



        s1.pop_back();

        if(n==1)
        {
            cout<<s1<<endl;
            continue;
        }

        ll temp=0;

        for(i=0;i<s1.size();i++)
        {
            if(s1[i]>='a'&&s[i]<='z')
            {
                m[i]=temp;
            }
            else
            {
                temp++;
                m[i]=temp;
            }
        }

        vector<ll>sa=BuildSuffixArray(s1);
        vector<ll>lc=lcp(sa,s1);

        ll l=0,r=1;
        ll ans=1;

       // debug(n);
        //debug(sa);

        multiset<ll>st;

        st.in(m[sa[0]]);
        st.in(m[sa[1]]);

        while(r<sa.size())
        {
            set<ll>y;

            for(auto x:st )
            {
                y.in(x);
            }

            if(y.size()==n)
            {
                ll val=lcp(l,r,lc);
                ans=max(ans,val);
                st.erase(m[sa[l]]);
                l++;

                if(l<sa.size())
                    st.in(m[sa[l]]);
                else
                    break;
            }
            else
            {
                r++;

                if(r<sa.size())
                    st.in(m[sa[r]]);
            }

        }




        cout<<ans<<endl;


    }

}