Given n words w[1..n], which originate from the same stem (e.g. grace, graceful, disgraceful, gracefully), we are interested in the original stem. To simplify the problem, we define the stem as the longest consecutive substring that occurs in all the n words. If there are ties, we will choose the smallest one in the alphabetical (lexicographic) order.

-----Input-----
The first line contains an integer T denoting the total number of test cases.
In each test cases, the first line contains an integer n denoting the number of words. In the second line, n words w[1..n] consisting of lower case characters are given as a single space-spearated list.

-----Output-----
For each test case, output the stem in a new line.

-----Constraints-----
- 1 <= T <= 10
- 1 <= n <= 10
- 1 <= |w[i]| <= 20

-----Example-----
Input:
1
4
grace graceful disgraceful gracefully
Output:
grace

-----Explanation-----
The stem is grace.

Difficulty: interview

Starter code:

Solutions:
t = eval(input())
for _ in range(t):
 n = eval(input())
 a = input().strip().split()
 cb, cs = 0, ""
 for i in range(len(a[0])):
  for j in range(i+1,len(a[0])+1):
   al = True
   s = a[0][i:j]
   for k in a[1:]:
    if s not in k:
     al = False
     break
   if al:
    if j-i>=cb:
     cb = max(cb, j-i)
     if len(cs) < cb:
      cs = a[0][i:j]
     elif len(cs) == cb:
      cs = min(cs,a[0][i:j])
 print(cs)

s = [ ]

def chk(st,n):
  for x in s:
    if st not in x :
      return 0
  return 1

for t in range(eval(input())):
  n=eval(input())
  s = list( input().split() )
  
  mx = -1
  ans = ""
  
  for i in range(len(s[0])):
    for j in range(i,len(s[0])):
      if chk( s[0][i:j+1], n ):
        if mx == j+1-i :
          ans = min( ans, s[0][i:j+1] )
        if mx < j+1-i :
          mx = j+1-i
          ans = s[0][i:j+1]
  
  print(ans)

import sys

for __ in range(eval(input())):
 n = eval(input())
 lists = list(map(str,sys.stdin.readline().split()))
 lists.sort(key=lambda x:len(x))
 stem , stems = lists[0] , []
 for k in range(len(lists[0])) :
  for j in range(k+1,len(lists[0])) :
   ctr = 0
   for i in lists[1:] :
    if stem[k:j+1] in i :
     ctr += 1
   if ctr == n-1 :
    stems.append(stem[k:j+1])
 
 stems.sort(key=lambda x:len(x),reverse = True)
 stems = [x for x in stems if len(x)==len(stems[0])]
 stems.sort()
 print(stems[0] if len(stems)>0 else "")


 # your code goes here
t = int(input())
while(t>0):
 n = int(input())
 s = input().split(" ")
 dic = {} 
 for i in range(len(s[0])):
  for j in range(i,len(s[0])):
   dic[s[0][i:j+1]]=1
#   print dic
 for i in range(1,len(s)):
  for j in range(len(s[i])):
   for k in range(j,len(s[i])):
    x = dic.get(s[i][j:k+1],-1)
    if(x==i):
     dic[s[i][j:k+1]]+=1
  #//print dic
 ans = ""
 #print "SsSSSSS"
 #print dic
 for x in dic:
  if(dic[x]==n):
   if(len(x)>=len(ans)):
    ans = x
 for x in dic:
  if(len(x) == len(ans) and dic[ans] == dic[x]):
   ans = min(ans,x)
 print(ans)
 t-=1

t=int(input())
while t>0:
 t-=1
 l1=["" for _ in range(21)]
 n=int(input())
 l=input().split()
 ma=0
 ans=""
 for i in range(0,len(l[0])):
  s=""
  for j in range(i,len(l[0])):
   s+=l[0][j]
   fl=1
   for k in range(1,len(l)):
    if s not in l[k]:
     fl=0
   if fl:
    le=len(s)
    if l1[le]=="":
     l1[le]=s
    else:
     l1[le]=min(l1[le],s)
    #print s,l1
 for i in range(20,0,-1):
  if l1[i]!="":
   ans=l1[i]
   break
 print(ans)

t = int(input())
for _ in range(t):
 best = ''
 n = int(input())
 words = input().split()
 min = 20
 min_index = 0
 for i, word in enumerate(words):
  if len(word) < min:
   min = len(word)
   min_index = i
 for i in range(min, 0, -1):
  found = False
  for j in range(min-i+1):
   all = True
   sub = words[min_index][j:j+i]
   for word in words:
    if sub not in word:
     all = False
     break
   if all:
    if best == '' or best>sub:
     best = sub
     found = True
  if found:
   break
 print(best)




t=eval(input())
while t:
 t-=1
 ans=[]
 n=eval(input())
 ls=input().split(' ')
 l=len(ls[0])
 for i in range(l):
  for j in range(i,l+1):
   tmp=ls[0][i:j]
#            print tmp
   flg=0
   for k in range(n):
    if ls[k].count(tmp)>0 and len(tmp)>0:
     pass
    else:
     flg=1
   if flg==0:
    ans.append(tmp)
#    print ans
 ans=sorted(ans)
 print(max(ans,key=len))


for i in range(eval(input())):
 n=eval(input())
 w=input().split()
 q=[]
 q.append(w[0])
 p=q[0]
 l=len(p)
 for j in range(l-1,0,-1):
  for k in range(0,l-j+1):
   q.append(p[k:k+j])
 ans=[]
 l=0
 for j in q:
  ct=0
  if(l>len(j)):
   break
  
  for k in w:
   if(k.find(j)!=-1):
    ct+=1
    
  if(ct==n):
   ans.append(j)
   l=len(j)
   
 print(min(ans))
 
   
  
    
    
     


t=int(input())
while t>0:
 n=int(input())
 s=input()
 words=s.split()
#    print words
 substrings=[]
 for i in words:
  tmp=[]
  for j in range(len(i)):
   for k in range(j+1,len(i)+1):
    tmp.append(i[j:k])
  substrings.append(tmp)
#    print substrings[0]
 stem=""
 for i in substrings[0]:
  flag=True
  for j in words:
   if i not in j:
    flag=False
  if(flag==True and len(i)>len(stem)):
   stem=i
  elif(flag==True and len(i)==len(stem) and i<stem):
   stem=i
 print(stem)
 t=t-1 

def sub(s1, s2):
 m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
 longest, x_longest = 0, 0
 for x in range(1, 1 + len(s1)):
  for y in range(1, 1 + len(s2)):
   if s1[x - 1] == s2[y - 1]:
    m[x][y] = m[x - 1][y - 1] + 1
    if m[x][y] > longest:
     longest = m[x][y]
     x_longest = x
   else:
    m[x][y] = 0
 return s1[x_longest - longest: x_longest]

test = eval(input())
while test:
  test-=1
  n = eval(input())
  arr1 = list(map(str,input().split()))
  arr = []
  for i in range(n):
    ans = arr1[i]
    for j in range(n):
      ans = sub(ans, arr1[j])
    arr.append(ans)
  oth_arr =[]
  length = 0
  for i in range(len(arr)):
    length = max(length, len(arr[i]))
  for i in range(len(arr)):
    if len(arr[i])==length:
      oth_arr.append(arr[i]) 
  oth_arr.sort()
  print(oth_arr[0])
  


t = int(input())
for _ in range(t):
 n = int(input())
 w = input().split()
 x = w.pop(0)
 l = len(x)
 ans = ""
 for i in range(l):
  for j in range(i, l+1):
   common = True
   sub = x[i:j]
   for string in w:
    if sub not in string:
     common = False
     break
   if common:
    if len(sub) > len(ans) or (len(sub) == len(ans) and ans > sub):
     ans = sub
 print(ans)


T = int(input())

while T>0:
 n = int(input())
 words = input().split()
 words.sort(key = lambda s: len(s))
 temp = words[0]
 l = len(temp)
 
 ans = []
 for i in range(0,l+1):
  ans = []
  for j in range(0,i+1):
   t = temp[j:l-i+j]
   check = True
   for k in range(1,n):
    if t in words[k]:
     continue
    else :
     check =False
     break
   if check:
    ans.append(t)
  
  if len(ans)>0:
   break
 
 ans.sort()
 print(ans[0])
 
 T =T-1

# STEM.py

def main():
 t = int(input())
 for _ in range(t):
  n = int(input())
  arr = input().split();      
  min_length = 30;
  index = -1;
  for i in range(n):
   x = arr[i];     
   # print x,len(x)    
   if len(x) < min_length:
    index = i;
    min_length = len(x);

  
  s = arr[index];
  # print s
  # max_len = len(s)+1;
  answers = []
  l = len(s);
  while l > 0:
   for i in range(len(s)):            
    if i+l > len(s):
     break;
    flag = True;
    sub = s[i:i+l];

    for j in arr:
     if j.find(sub) == -1:
      # print sub,j
      flag = False;
      break;
    if flag :
     # print 'Answer Found',sub
     answers.append(sub);
   l -=1;
   if len(answers) > 0 :
    break;

  
  answers.sort();     
  print((answers[0]));
main();


t=int(input())
while(t>0):
 n=int(input())
 tcase=input().split(' ')
 ans=''
 alen=0
 for i in range(len(tcase[0])+1):
  for j in range(i+1):
   if all(tcase[0][j:i] in b for b in tcase):
    if(len(tcase[0][j:i])>alen):
     ans=tcase[0][j:i]
     alen=len(ans)
    elif len(tcase[0][j:i])==alen:
     if tcase[0][j:i]<ans:
      ans=tcase[0][j:i]
 print(ans)
 t=t-1 



# your code goes here

t = int(input())
for i in range(t):
 n = int(input())
 words = input().split()
 ans = ''
 for i in range(0, len(words[0])):
  for j in range(i+1, len(words[0])+1):
   found = True
   for word in words[1:]:
    if not words[0][i:j] in word:
     found = False
     break
   if found:
    if len(ans) == len(words[0][i:j]) and ans > words[0][i:j]:
     ans = words[0][i:j]
    elif len(ans) < len(words[0][i:j]):
     ans = words[0][i:j]
 print(ans)
    


t = int(input())
for _i in range(t):
 n = int(input())
 words = input().split()
 
 words = sorted(words, key=lambda x: len(x))
 mw = words[0]
 words = words[1:]
 
 ans,alen = '',0
 for i in range(len(mw)):
  for j in range(i,len(mw)):
   ss = mw[i:j+1]
   
   found = True 
   for word in words:
    if ss not in word:
     found = False
     break
   
   if found:
    if len(ss) > alen:
     ans,alen = ss,len(ss)
    elif len(ss) == alen and ss < ans:
     ans,alen = ss,len(ss)
 
 print(ans)


t = eval(input())
while t != 0:
 md = {}
 t -= 1
 n = eval(input())
 wrds = input().split()
 c = 0
 for w in wrds:
  c += 1
  for i in range(len(w)):
   for j in range(i,len(w)):
    sub = w[i:j+1]
    if sub not in md:
     md[sub] = 1
    elif sub in md and md[sub] == c-1:
     md[sub] = c 
 res = ""
 for k in list(md.keys()):
  if md[k] == n:
   if len(k) > len(res):
    res = k
   elif len(k) == len(res) and k < res:
    res = k
 print(res)



t = int(input())
for tc in range(t):
 n = int(input())
 stem = ''
 arr = input().split()
 size = len(arr[0])
 max_length = 0
 for i in range(size):
  for j in range(i, size+1):
   temp = arr[0][i:j]
   check = True 
   for x in range(1, n):
    if temp in arr[x]:
     pass
    else:
     check = False
   if check:
    if max_length < j-i+1:
     stem = temp
     max_length = j-i+1
    elif max_length == j-i+1 and stem > temp:
     stem = temp
 print(stem)