Problem Description

You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.

 

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string. 

 

Output

There should be one line per test case containing the length of the largest string found.

 

Sample Input

 

Sample Output

 

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

#define ll long long int

using namespace std;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int moth[]={,,,,,,,,,,,,};

int dir[][]={, ,, ,-, ,,-};

int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

int nextt[];

bool vis[];

void getnext(string s){

    nextt[]=;

    int len=s.length();

    for(int i=,j=;i<=len;i++){

        while(j>&&s[i-]!=s[j]) j=nextt[j];

        if(s[i-]==s[j]) j++;

        nextt[i]=j;

    }

}

bool kmp(string t,string p){

    int len1=p.length();

    int len2=t.length();

    for(int i=,j=;i<=len1;i++){

        while(j>&&p[i-]!=t[j]) j=nextt[j];

        if(p[i-]==t[j]) j++;

        if(j==len2)

        return true;

    }

    return false;

}

string s[];

int main(){

    ios::sync_with_stdio(false);

    int t;

    cin>>t;

    while(t--){

        int n;

        cin>>n;

        for(int i=;i<=n;i++)

            cin>>s[i];

        int len=s[].length();

        //cout<<len<<endl;

        int ans=;

        for(int i=;i<=len;i++){

            for(int j=;j<=len-i;j++){

                string temp=s[].substr(j,i);

                getnext(temp);

                bool f=;

                for(int k=;k<=n;k++){

                    string pre=s[k];

                    if(kmp(temp,pre)) continue;

                    reverse(pre.begin(),pre.end());

                    if(kmp(temp,pre)) continue;

                    f=;

                    break;

                }

                if(f) ans=max(ans,i);

            }

        }

        cout<<ans<<endl;

    }

    return ;

}