Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef recently visited ShareChat Cafe and was highly impressed by the food. Being a food enthusiast, he decided to enquire about the ingredients of each dish.

There are $N$ dishes represented by strings $S_{1}, S_{2}, \ldots, S_{N}$. Each ingredient used for making dishes in ShareChat Cafe is represented by a lowercase English letter. For each valid $i$, the ingredients used to make dish $i$ correspond to characters in the string $S_{i}$ (note that ingredients may be used multiple times). A *special ingredient* is an ingredient which is present in each dish at least once.

Chef wants to know the number of special ingredients in ShareChat Cafe. Since Chef is too busy with work, can you help him?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains a single string $S_{i}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of special ingredients in the dishes.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 1,000$
$1 ≤ |S_{i}| ≤ 200$ for each valid $i$
$S_{1}, S_{2}, \ldots, S_{N}$ contain only lowercase English letters
The sum of length of strings over all test cases $≤$ 3500000

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2

3

abcaa

bcbd

bgc

3

quick

brown

fox
----- Sample Output 1 ------ 
2

0
----- explanation 1 ------ 
Example case 1: Ingredients 'b' and 'c' are present in all three dishes, so there are two special ingredients.

Example case 2: No ingredient is common to all three dishes.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		s = input()
		s = set(list(s))
		l.append(s)
	a = l[0]
	for i in l[1:]:
		a = a.intersection(i)
	print(len(a))


for _ in range(int(input())):
	n = int(input())
	s = set()
	for i in range(n):
		if i:
			s = s.intersection(set(input()))
		else:
			s = set(input())
	print(len(s))


for _ in range(int(input())):
	dish_list = []
	for i in range(int(input())):
		dish = input()
		dish_list.append(set(list(dish)))
	dish = dish_list[0]
	for k in dish_list[1:]:
		dish = dish.intersection(k)
	print(len(dish))


from collections import Counter
t = int(input())
for ojfeu in range(t):
	n = int(input())
	a = []
	for iodf in range(n):
		x = list(set(str(input())))
		a.extend(x)
	x = Counter(a)
	c = 0
	for j in x:
		if x[j] == n:
			c += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	c = ''
	s = ''
	d = {}
	for i in range(n):
		a = input()
		b = set(a)
		s += c.join(b)
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	q = 0
	for (k, v) in d.items():
		if v == n:
			q += 1
	print(q)


T = int(input())
for i in range(T):
	a = [0] * 26
	l = []
	x = int(input())
	for j in range(x):
		s = input()
		s = set(list(s))
		l.append(s)
	for i in l:
		for j in i:
			a[ord(j) - ord('a')] += 1
	if x in a:
		print(a.count(x))
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	d = {}
	for i in range(n):
		n1 = input()
		ss = set(n1)
		for i in ss:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	c = 0
	for i in d.values():
		if i == n:
			c += 1
	print(c)


t = int(input())
for i in range(1, t + 1):
	x = int(input())
	d = {}
	for i in range(x):
		s = input()
		s = set(s)
		for j in s:
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
	c = 0
	for i in d.values():
		if i == x:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	d = {}
	for i in range(n):
		a = input()
		k = set(a)
		for i in k:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	c = 0
	for i in d.values():
		if i % n == 0:
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = [0] * 26
	for i in range(n):
		s = input()
		d = set(s)
		for j in d:
			a[ord(j) - 97] += 1
	c = 0
	for q in a:
		if q == n:
			c += 1
	print(c)


for i in range(int(input())):
	N = int(input())
	w = input()
	s = set(w)
	c = 0
	arr = []
	for k in range(1, N):
		arr.append(input())
	for m in s:
		for l in arr:
			if m not in l:
				break
		else:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	a = [0] * 26
	for i in range(n):
		str = input()
		s = set(str)
		for i in s:
			a[ord(i) - 97] += 1
	c = 0
	for i in range(len(a)):
		if a[i] == n:
			c += 1
	print(c)


for i in range(int(input())):
	d = int(input())
	k = []
	for i in range(d):
		s = input()
		s = set(list(s))
		k.append(s)
	a = k[0]
	for i in k[1:]:
		a = a.intersection(i)
	print(len(a))


T = int(input())
for i in range(T):
	N = int(input())
	a = [0] * 26
	for i in range(N):
		str = input()
		s = set(str)
		for i in s:
			a[ord(i) - 97] += 1
	cnt = 0
	for i in range(len(a)):
		if a[i] == N:
			cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	Dict = {}
	for j in range(n):
		l.append(input())
		s = set()
		for k in l[j]:
			s.add(k)
		for k in s:
			if k in Dict:
				Dict[k] += 1
			else:
				Dict[k] = 1
		s.clear()
	count = 0
	for (key, value) in Dict.items():
		if value == n:
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	lst = []
	for i in range(n):
		s = input()
		s = set(list(s))
		lst.append(s)
	a = lst[0]
	for i in lst:
		a = a.intersection(i)
	print(len(a))


t = int(input())
for i in range(t):
	n = int(input())
	dish_dict = {}
	NextList = set()
	for j in range(n):
		Prevlist = set()
		dish = input()
		Mylist = []
		for ch in dish:
			Prevlist.add(ch)
		if j != 0:
			for ele in Prevlist:
				if ele in NextList:
					Mylist.append(ele)
			NextList = Mylist
		else:
			NextList = Prevlist
	print(len(NextList))


t = int(input())
for i in range(t):
	n = int(input())
	li = []
	ans = 0
	for j in range(n):
		str1 = input()
		li.append(str1)
	for k in range(26):
		s = 0
		c = chr(97 + k)
		for x in li:
			if c in x:
				s += 1
		if s == n:
			ans += 1
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	i = 0
	list1 = []
	m = 0
	f = 0
	while i < n:
		s = input()
		l = len(s)
		if f == 0:
			m = l
			st = s
			f = 1
		elif l < m:
			m = l
			st = s
		list1.append(s)
		i = i + 1
	c = 0
	fla = 0
	list5 = []
	for i in st:
		if i not in list5:
			list5.append(i)
			fla = 0
			for j in list1:
				if i in j:
					fla = 1
				else:
					fla = -1
					break
			if fla == 1:
				c = c + 1
	print(c)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(set(input()))
	word = l[0]
	count = 0
	for i in word:
		for j in l:
			if i not in j:
				break
		else:
			count += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(set(input()))
	word = l[0]
	count = 0
	for j in l[1:]:
		word = word.intersection(j)
	print(len(word))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(set(input()))
	for j in range(n - 1):
		unique = []
		s = input()
		s = list(set(s))
		for k in l:
			if k in s:
				unique.append(k)
		l = unique
	print(len(l))


a = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}
for i in range(int(input())):
	N = int(input())
	l_st = []
	for i in range(N):
		string = set(input())
		l_st.append(string)
		if i == 0:
			shk = a & l_st[i]
		else:
			shk = shk & l_st[i]
	print(len(shk))


T = int(input())
for _ in range(0, T):
	n = int(input())
	s1 = str(input())
	l = list(s1)
	l = [*set(l)]
	for i in range(1, n):
		s = str(input())
		w = 0
		while w < len(l):
			if l[w] not in s:
				l.remove(l[w])
			else:
				w += 1
	print(len(l))


a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(int(input())):
	n = int(input())
	s = set(a)
	l = []
	for j in range(n):
		st = input()
		l.append(set(st))
		s = s & l[j]
	print(len(s))


for _ in range(int(input())):
	n = int(input())
	l = dict()
	ans = 0
	for i in range(n):
		s = input()
		d = dict()
		for j in s:
			if j not in d:
				d[j] = 1
		for j in d:
			if j in l:
				l[j] += 1
			else:
				l[j] = 1
	for j in l:
		if l[j] >= n:
			ans += 1
	print(ans)


for test_ in range(int(input())):
	n = int(input())
	food = []
	for i in range(n):
		food.extend([*set(input())])
	d = {}
	for i in [*food]:
		d[i] = d.get(i, 0) + 1
	count = 0
	for (k, v) in d.items():
		if v == n:
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	lis = []
	for i in range(n):
		s = list(input())
		lis.append(s)
	x = []
	for i in range(len(lis)):
		for j in range(len(lis[i])):
			x.append(lis[i][j])
	z = list(set(x))
	q = []
	for i in range(len(lis)):
		for j in range(len(z)):
			if z[j] not in lis[i]:
				q.append(z[j])
	p = []
	for i in range(len(z)):
		if z[i] not in q:
			p.append(z[i])
	print(len(p))


t = int(input())
for _ in range(t):
	n = int(input())
	lis = []
	for i in range(n):
		s = input()
		lis.append(s)
	lis1 = []
	for i in range(len(lis)):
		l = list(lis[i])
		ls = list(set(l))
		x = ''.join(ls)
		lis1.append(x)
	y = ''.join(lis1)
	lisf = []
	for i in range(len(y)):
		if y.count(y[i]) >= n:
			lisf.append(y[i])
	print(len(list(set(lisf))))


for i in range(int(input())):
	n = int(input())
	m = {}
	res = 0
	for j in range(n):
		s = input()
		d = {}
		for k in s:
			if k not in d:
				d[k] = 1
		for k in d:
			if k not in m:
				m[k] = 1
			else:
				m[k] += 1
	for j in m:
		if m[j] >= n:
			res += 1
	print(res)


for x in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		data = input()
		data = list(set(data))
		a.append(data)
	s = a[0]
	final = 0
	for char in s:
		count = 0
		for i in range(1, len(a)):
			name = a[i]
			if char in name:
				count += 1
		if count == n - 1:
			final += 1
	print(final)


for _ in range(int(input())):
	n = int(input())
	lst = []
	for _ in range(n):
		lst.append(input())
	lst = [set(x) for x in lst]
	res = lst[0]
	for s in lst[1:]:
		res = s & res
	print(len(res))


for i in range(int(input())):
	n = int(input())
	ma = {}
	ans = 0
	for j in range(n):
		s = input()
		d = {}
		for k in s:
			if k not in d:
				d[k] = 1
		for k in d:
			if k not in ma:
				ma[k] = 1
			else:
				ma[k] += 1
	for j in ma:
		if ma[j] >= n:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(n):
		s = input()
		for j in s:
			if i == 0 and j not in d:
				d[j] = 1
			elif i == 0 and j in d:
				d[j] = d[j] + 1
			elif j in d:
				d[j] = min(d[j], s.count(j))
		item = list(d.keys())
		for x in item:
			if x not in s:
				del d[x]
	print(len(d))


for _ in range(int(input())):
	n = int(input())
	s = []
	emp = ''
	for i in range(n):
		s.append(input())
		emp += s[i]
	li = [i for i in emp]
	li = list(set(emp))
	cnt = 0
	for i in li:
		a = 0
		for j in s:
			if i in j:
				a += 1
		if a == n:
			cnt += 1
	print(cnt)


u = int(input())
for _ in range(u):
	b = int(input())
	dic = {}
	k = input()
	for ch in k:
		dic[ch] = 1
	for i in range(b - 1):
		k = input()
		for ch in k:
			if ch in dic and dic[ch] == i + 1:
				dic[ch] += 1
	nb = 0
	for i in dic.values():
		if i == b:
			nb += 1
	print(nb)


t = int(input())
for _ in range(t):
	n = int(input())
	dic = {}
	s = input()
	for ch in s:
		dic[ch] = 1
	for i in range(n - 1):
		s = input()
		for ch in s:
			if ch in dic and dic[ch] == i + 1:
				dic[ch] += 1
	nb = 0
	for i in dic.values():
		if i == n:
			nb += 1
	print(nb)


t = int(input())
for z in range(t):
	d = {}
	n = int(input())
	for i in range(n):
		a = set(input())
		for j in a:
			if j not in d:
				d[j] = 1
			else:
				d[j] += 1
	x = 0
	for i in d:
		if d[i] == n:
			x += 1
	print(x)


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		var = list(set(input()))
		var = ''.join(var)
		arr.append(var)
	new = ''.join(arr)
	cnt = 0
	mp = {}
	for i in range(len(new)):
		if new[i] not in mp:
			mp[new[i]] = 1
		else:
			mp[new[i]] += 1
	for val in mp.values():
		if val >= n:
			cnt += 1
	print(cnt)


t = input()
for c in range(0, int(t)):
	numberOfDishes = int(input())
	specialDishes = []
	specialDishesCount = 0
	for x in range(numberOfDishes):
		specialDishes.append(input())
	common = set.intersection(*map(set, specialDishes))
	print(len(common))


u = int(input())
for i in range(0, u):
	v = int(input())
	for i in range(0, v):
		if i == 0:
			f = input()
			e = set(f)
		else:
			f = input()
			e = e.intersection(set(f))
	print(len(e))


for _ in range(int(input())):
	n = int(input())
	s = []
	t = ''
	for i in range(n):
		s.append(input())
		t += s[i]
	l = [i for i in t]
	l = list(set(l))
	ans = 0
	for i in l:
		c = 0
		for j in s:
			if i in j:
				c += 1
		if c == n:
			ans += 1
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	for i in range(0, n):
		if i == 0:
			y = input()
			s = set(y)
		else:
			y = input()
			s = s.intersection(set(y))
	print(len(s))


for i in range(int(input())):
	n = int(input())
	k = []
	for i in range(n):
		s = input()
		arr = []
		if i == 0:
			a = []
			for item in s:
				if item not in k:
					k.append(item)
			for item in k:
				a.append(item)
		else:
			for item in s:
				if item not in arr:
					arr.append(item)
			if len(k) > 0:
				for j in a:
					if j in arr:
						continue
					elif j in k:
						k.remove(j)
	print(len(k))


for i in range(int(input())):
	N = int(input()) - 1
	common = {*input()}
	for i in range(N):
		dish = {*input()}
		common = common.intersection(dish)
	print(len(common))


n = int(input())
x = []
for i in range(0, n):
	l = int(input())
	arr0 = [0] * 50
	for j in range(0, l):
		inp = input()
		inp = list(set(inp))
		for k in range(0, len(inp)):
			arr0[ord(inp[k]) - 97] += 1
	count = 0
	for j in arr0:
		if j >= l:
			count += 1
	x.append(count)
for i in x:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	res = set(input())
	for j in range(n - 1):
		s = set(input())
		res = res.intersection(s)
	print(len(res))


for _ in range(int(input())):
	n = int(input())
	s = 'abcdefghijklmnopqrstuvwxyz'
	arr = []
	unique = []
	for i in range(n):
		arr.append(input())
	for i in range(26):
		x = s[i]
		exist = True
		for j in arr:
			if x not in j:
				exist = False
				break
		if exist:
			unique.append(x)
	print(len(unique))