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: UNKNOWN_DIFFICULTY

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 '')


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
	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
	ans = ''
	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)
	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]
			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)
	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()
	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)
	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


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]
			if len(x) < min_length:
				index = i
				min_length = len(x)
		s = arr[index]
		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:
						flag = False
						break
				if flag:
					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


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)