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

Сhef has assembled a football team! Now he needs to choose a name for his team. There are $N$ words in English that Chef considers *funny*. These words are $s_{1}, s_{2}, \dots, s_{N}$.

Chef thinks that a good team name should consist of two words such that they are not funny, but if we swap the first letters in them, the resulting words are funny. Note that under the given constraints, this means that a word is a non-empty string containing only lowercase English letters.

Can you tell Chef how many good team names there are?

------  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$.
The second line contains $N$ space-separated strings $s_{1}, s_{2}, \ldots, s_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the number of ways to choose a good team name.

------  Constraints ------
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 2 \cdot 10^{4}$
$2 ≤ |s_{i}| ≤ 20$ for each valid $i$
$s_{1}, s_{2}, \ldots, s_{N}$ contain only lowercase English letters
$s_{1}, s_{2}, \ldots, s_{N}$ are pairwise distinct
the sum of $N$ over all test cases does not exceed $2 \cdot 10^{4}$

------  Subtasks ------
Subtask #1 (20 points): $s_{1}, s_{2}, \ldots, s_{N}$ contain only letters 'a' and 'b'

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
3

2

suf mas

3

good game guys

4

hell bell best test
----- Sample Output 1 ------ 
2

0

2
----- explanation 1 ------ 
Example case 1: The good team names are ("muf", "sas") and ("sas", "muf").

Example case 2: There are no good team names because all funny words start with 'g'.

Example case 3: The good team names are ("hest", "tell") and ("tell", "hest").

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Implementation


Solutions:
for test in range(int(input())):
	n = int(input())
	nlist = input().split()
	d = {}
	for i in nlist:
		try:
			d[i[1:]].add(i[0])
		except KeyError:
			d[i[1:]] = set()
			d[i[1:]].add(i[0])
	tlist = list(d.keys())
	n1 = len(tlist)
	ans = 0
	for i in range(n1):
		for j in range(i + 1, n1):
			total = d[tlist[i]].union(d[tlist[j]])
			ans += len(total.difference(d[tlist[j]])) * len(total.difference(d[tlist[i]]))
	print(ans * 2)


for _ in range(int(input())):
	n = int(input())
	s = input().split()
	(d, c) = ({}, 0)
	for i in s:
		b = i[1:]
		if b not in d:
			d[b] = [i[0]]
		else:
			d[b].append(i[0])
	lst = list(d.keys())
	for i in range(len(d)):
		for j in range(i + 1, len(d)):
			l = len(set(d[lst[i]] + d[lst[j]]))
			c += (l - len(d[lst[i]])) * (l - len(d[lst[j]]))
	print(2 * c)


for z in range(int(input())):
	n = int(input())
	s = [x for x in input().split()]
	d = [set() for i in range(26)]
	k = set()
	for x in s:
		k.add(ord(x[0]) - 97)
		d[ord(x[0]) - 97].add(x[1:])
	c = 0
	k = list(k)
	for i in range(len(k)):
		for j in range(i + 1, len(k)):
			l = len(d[k[i]].intersection(d[k[j]]))
			c += (len(d[k[i]]) - l) * (len(d[k[j]]) - l)
	print(2 * c)


def snak(c1, c2):
	s = len(set(c1 + c2))
	return s

def snek(f):
	d = {}
	for i in f:
		r = i[1:]
		if r in d:
			d[r].append(i[0])
		else:
			d[r] = [i[0]]
	return d
t = int(input())
for i in range(t):
	n = int(input())
	f = input().split()
	d1 = snek(f)
	d2 = list(d1.keys())
	s = 0
	for j in range(len(d1)):
		for k in range(j + 1, len(d1)):
			a = snak(d1[d2[j]], d1[d2[k]])
			s += (a - len(d1[d2[j]])) * (a - len(d1[d2[k]]))
	print(2 * s)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	str1 = s.split()
	code = {}
	for w in str1:
		key = w[1:]
		val = w[0]
		if key in code:
			code[key].append(val)
		else:
			code[key] = list(val)
	ends = list(code.keys())
	c = 0
	for i in range(len(code)):
		for j in range(i + 1, len(code)):
			t = len(set(code[ends[i]] + code[ends[j]]))
			c += (t - len(code[ends[i]])) * (t - len(code[ends[j]]))
	print(2 * c)


def uniq(l1, l2):
	s = len(set(l1 + l2))
	return s

def create(funny):
	dicto = {}
	for i in funny:
		rest = i[1:]
		if rest in dicto:
			dicto[rest].append(i[0])
		else:
			dicto[rest] = [i[0]]
	return dicto
t = int(input())
for x in range(t):
	n = int(input())
	funny = input().split()
	dic = create(funny)
	dic1 = list(dic.keys())
	s = 0
	for i in range(len(dic)):
		for j in range(i + 1, len(dic)):
			temp = uniq(dic[dic1[i]], dic[dic1[j]])
			s += (temp - len(dic[dic1[i]])) * (temp - len(dic[dic1[j]]))
	print(2 * s)


import sys
input_ = lambda : sys.stdin.readline().strip('\r\n')
iip = lambda : int(input_())
ip = lambda : input_()
pri = lambda x: print(x)
for _ in range(iip()):
	n = iip()
	a = ip().split()
	total = 0
	locate = {}
	for i in range(n):
		locate[a[i]] = True
	cha = [[] for i in range(26)]
	for i in range(n):
		cha[ord(a[i][0]) - 97].append(a[i][1:])
	for i in range(25):
		for j in range(i + 1, 26):
			if len(cha[i]) > 0 and len(cha[j]) > 0:
				for k in range(len(cha[i])):
					x = chr(97 + j) + cha[i][k]
					if locate.get(x):
						continue
					for l in range(len(cha[j])):
						y = chr(97 + i) + cha[j][l]
						if locate.get(y):
							pass
						else:
							total += 1
	pri(total * 2)


def same(x1, x2):
	arr = set.intersection(set(x1), set(x2))
	ans = len(list(arr))
	return ans
T = int(input())
for i in range(T):
	N = int(input())
	s = input().split()
	dic = {}
	for j in s:
		rest = j[1:]
		if rest in dic:
			dic[rest].append(j[0])
		else:
			dic[rest] = [j[0]]
	res = 0
	dic1 = list(dic.keys())
	for j in range(len(dic)):
		for k in range(j + 1, len(dic)):
			tmp = same(dic[dic1[j]], dic[dic1[k]])
			res += (len(dic[dic1[j]]) - tmp) * (len(dic[dic1[k]]) - tmp)
	print(res * 2)


t = int(input())
for _ in range(t):
	n = int(input())
	w = input().split()
	k = set(w)
	letters = []
	d = {}
	for word in w:
		letters.append(word[0])
	for letter in letters:
		d[letter] = []
	for word in w:
		d[word[0]].append(word[1:])
	letters = list(set(letters))
	ans = 0
	for word in w:
		for letter in letters:
			if letter + word[1:] not in k:
				for suff in d[letter]:
					if word[0] + suff not in k:
						ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	array = set(list(map(str, input().split())))
	(pre, precnt) = ({}, {})
	for i in array:
		try:
			precnt[i[0]] += 1
			pre[i[0]].add(i[1:])
		except KeyError:
			precnt[i[0]] = 1
			pre[i[0]] = {i[1:]}
	answer = 0
	for i in pre:
		for j in pre:
			c = len(pre[i].intersection(pre[j]))
			answer += (precnt[i] - c) * (precnt[j] - c)
	print(answer)


for _ in range(int(input())):
	n = int(input())
	l = list(map(str, input().split()))
	k = dict.fromkeys(l, 1)
	k1 = {}
	k2 = {}
	for i in l:
		try:
			k1[i[1:]] += 1
			k2[i[1:]].add(i[0])
		except KeyError:
			k1[i[1:]] = 1
			k2[i[1:]] = {i[0]}
	ans = 0
	for i in k2:
		for j in k2:
			c = len(k2[i].intersection(k2[j]))
			ans += (k1[i] - c) * (k1[j] - c)
	print(ans)


def com(a, b):
	return len(set(a + b))
for _ in range(int(input())):
	n = int(input())
	a = input().split()
	b = {}
	for i in a:
		x = i[1:]
		if x in b:
			b[x].append(i[0])
		else:
			b[x] = [i[0]]
	c = list(b.keys())
	ans = 0
	for i in range(len(c)):
		for j in range(i + 1, len(c)):
			temp = com(b[c[i]], b[c[j]])
			ans += (temp - len(b[c[i]])) * (temp - len(b[c[j]]))
	print(ans * 2)


t = int(input())
while t:
	a = []
	names = []
	n = int(input())
	arr = list(input().split(' '))
	mp = {}
	cnt = 0
	for i in arr:
		if i[1:] in mp:
			mp[i[1:]][ord(i[0:1]) - 97] = 1
		else:
			s = [0] * 26
			s[ord(i[0:1]) - 97] = 1
			mp[i[1:]] = s
	key = mp.keys()
	val = [i for i in mp.values()]
	for i in range(len(mp) - 1):
		for j in range(i + 1, len(mp)):
			b = []
			for l in range(len(val[i])):
				if val[i][l] and val[j][l] == 0:
					for m in range(len(val[j])):
						if val[j][m] and val[i][m] == 0:
							b.append(chr(l + 97))
							b.append(chr(m + 97))
			a.extend(b)
	print(len(a))
	t -= 1


def distinct(l1, l2):
	s = len(set(l1 + l2))
	return s
for t in range(int(input())):
	n = int(input())
	l = input().split()
	body = {}
	for i in l:
		p = i[1:]
		if p in body:
			body[p].append(i[0])
		else:
			body[p] = [i[0]]
	body1 = list(body.keys())
	s = 0
	for i in range(len(body)):
		for j in range(i + 1, len(body)):
			temp = distinct(body[body1[i]], body[body1[j]])
			s += (temp - len(body[body1[i]])) * (temp - len(body[body1[j]]))
	print(2 * s)


t = int(input())
l = []
for i in range(t):
	n = int(input())
	s = list(input().split())
	d = {}
	for j in s:
		if j[1:] not in d:
			d[j[1:]] = {j[0]}
		else:
			d[j[1:]].add(j[0])
	keys = list(d.keys())
	ans = 0
	for j in range(len(keys)):
		for k in range(j + 1, len(keys)):
			comm = len(d[keys[j]].intersection(d[keys[k]]))
			ans += 2 * (len(d[keys[j]]) - comm) * (len(d[keys[k]]) - comm)
	l.append(ans)
for i in l:
	print(i)


for _ in range(int(input())):
	n = int(input())
	li = input().split(' ')
	suffix = {}
	for word in li:
		if word[1:] in suffix:
			suffix[word[1:]].add(word[0])
		else:
			suffix[word[1:]] = {word[0]}
	count = 0
	for suffix1 in suffix:
		for suffix2 in suffix:
			if suffix1 != suffix2:
				count_suf1 = len(suffix[suffix2] - suffix[suffix1])
				count_suf2 = len(suffix[suffix1] - suffix[suffix2])
				count += count_suf1 * count_suf2
	print(count)


def countSetBits(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	words = input().split(' ')
	key = 1
	prefix_map = {}
	count = 0
	suffix_map = {}
	for word in words:
		prefix_cur = word[0:1]
		suffix_cur = word[1:]
		if prefix_cur not in prefix_map.keys():
			prefix_map[prefix_cur] = key
			key = key << 1
		if suffix_cur in suffix_map.keys():
			suffix_map[suffix_cur] |= prefix_map[prefix_cur]
		else:
			suffix_map[suffix_cur] = prefix_map[prefix_cur]
	key -= 1
	for suffix in suffix_map.keys():
		suf_cur = suffix_map[suffix]
		for suffix1 in suffix_map.keys():
			suf_cur1 = suffix_map[suffix1]
			res = suf_cur ^ suf_cur1
			m = countSetBits(suf_cur & res)
			n = countSetBits(suf_cur1 & res)
			count += int(m * n)
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	arr = sorted(list(map(str, input().split())))
	temp = arr[0][0]
	keycount = 1
	dic = {'1': {arr[0][1:]}}
	for j in range(1, n):
		if temp == arr[j][0]:
			dic[str(keycount)].add(arr[j][1:])
		else:
			keycount += 1
			temp = arr[j][0]
			dic[str(keycount)] = {arr[j][1:]}
	c2 = 0
	for k in range(1, keycount):
		list1 = dic[str(k)]
		for m in range(k + 1, keycount + 1):
			list2 = dic[str(m)]
			count = len(list2.intersection(list1))
			c1 = (len(list1) - count) * (len(list2) - count)
			c2 += c1
	print(c2 * 2)


t = int(input())
for _ in range(t):
	input()
	m = set()
	A = input().split()
	for s in A:
		m.add(s)
	c = [0 for _ in range(26)]
	c2 = [[0 for __ in range(26)] for _ in range(26)]
	for s in A:
		f = ord(s[0])
		l = s[1:]
		c[f - ord('a')] += 1
		for char in range(ord('a'), ord('z') + 1):
			if char != f:
				st = chr(char) + l
				if st in m:
					c2[f - ord('a')][char - ord('a')] += 1
	ans = 0
	for i in range(26):
		for j in range(26):
			if i != j:
				ans += (c[i] - c2[i][j]) * (c[j] - c2[j][i])
	print(ans)


t = int(input())
for _ in range(t):
	input()
	m = {}
	for s in input().split():
		m.setdefault(s[1:], set()).add(s[0])
	ans = 0
	for s in m.values():
		for s1 in m.values():
			it = len(s1.intersection(s))
			ans += (len(s1) - it) * (len(s) - it)
	print(ans)


t = int(input())
for _ in range(t):
	input()
	m = {}
	A = input().split()
	for s in A:
		f = s[0]
		l = s[1:]
		m.setdefault(l, set()).add(f)
	p = []
	ans = 0
	for s in m.values():
		for s1 in m.values():
			if s != s1:
				it = len(s1.intersection(s))
				ans += (len(s1) - it) * (len(s) - it)
	print(ans)


def distinct(l1, l2):
	return len(set(l1 + l2))
t = int(input())
for i in range(t):
	n = int(input())
	strings = input().split()
	table = {}
	for item in strings:
		head = item[0]
		body = item[1:]
		if head in table:
			table[head].append(body)
		else:
			table[head] = [body]
	body1 = list(table.keys())
	ans = 0
	length = len(body1)
	for i in range(length - 1):
		for j in range(i + 1, length):
			temp = distinct(table[body1[i]], table[body1[j]])
			ans += (temp - len(table[body1[i]])) * (temp - len(table[body1[j]]))
	print(ans * 2)


def teamName(S):
	t = dict()
	for i in S:
		if i[1:] in t.keys():
			t[i[1:]].append(i[0])
		else:
			t[i[1:]] = [i[0]]
	name = 0
	l = list(t.values())
	for i in range(len(l)):
		for j in range(i + 1, len(l)):
			name += 2 * len(set(l[i]).difference(set(l[j]))) * len(set(l[j]).difference(set(l[i])))
	return name
for _ in range(int(input())):
	N = int(input())
	S = input().split()
	print(teamName(S))


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = list(map(str, input().split()))
		c = set()
		dic = {}
		ll = []
		for word in s:
			temp = word[1:]
			c.add(word[0])
			if temp not in dic:
				dic[temp] = {word[0]}
				ll.append(temp)
			else:
				dic[temp].add(word[0])
		if len(c) == 1:
			print(0)
			continue
		ans = 0
		for i in range(len(ll)):
			for j in range(i + 1, len(ll)):
				key1 = ll[i]
				key2 = ll[j]
				inter = dic[key1].intersection(dic[key2])
				cnt1 = len(dic[key1] - inter)
				cnt2 = len(dic[key2] - inter)
				ans += cnt1 * cnt2
		print(2 * ans)
except EOFError as t:
	pass


def diff(w1, w2):
	c = len(set(w1 + w2))
	return c
tests = int(input())
while tests:
	n = int(input())
	lt = input().split()
	names = {}
	for i in lt:
		last = i[1:]
		if last in names:
			names[last].append(i[0])
		else:
			names[last] = [i[0]]
	lt2 = list(names.keys())
	c = 0
	for i in range(len(names)):
		for j in range(i + 1, len(names)):
			temp = diff(names[lt2[i]], names[lt2[j]])
			c += (temp - len(names[lt2[i]])) * (temp - len(names[lt2[j]]))
	print(2 * c)
	tests -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(str, input().split()))
	st = {}
	tset = set()
	res = []
	for i in l:
		tset.add(i[0])
		if i[1:] in st:
			st[i[1:]].add(i[0])
		else:
			st[i[1:]] = {i[0]}
			res.append(i[1:])
	if len(tset) == 1:
		print(0)
		continue
	ans = 0
	for c in range(len(res)):
		for d in range(c + 1, len(res)):
			i = res[c]
			j = res[d]
			intr = st[i].intersection(st[j])
			si = len(st[i] - intr)
			sj = len(st[j] - intr)
			ans = ans + si * sj
	print(2 * ans)


test = int(input())
for _ in range(test):
	n = int(input())
	arr = input().split()
	suffixDict = {}
	for i in arr:
		if suffixDict.get(i[1:]) == None:
			suffixDict[i[1:]] = [i[0]]
		else:
			suffixDict[i[1:]].append(i[0])
	ans = 0
	iteratingArray = list(suffixDict.keys())
	for i in range(len(iteratingArray)):
		for j in range(i + 1, len(iteratingArray)):
			setA = set(suffixDict[iteratingArray[i]])
			setB = set(suffixDict[iteratingArray[j]])
			comm = len(setA.intersection(setB))
			ans += 2 * (len(setA) - comm) * (len(setB) - comm)
	print(ans)


from collections import OrderedDict
t = int(input())
for _ in range(t):
	n = int(input())
	l = input().split()
	dict = {a[1:]: set() for a in l}
	for a in l:
		dict[a[1:]].add(a[0])
	ans = 0
	visited = set()
	for f in dict:
		visited.add(f)
		for s in dict:
			if f != s and s not in visited:
				cf = 0
				cs = 0
				for i in dict[f]:
					if i not in dict[s]:
						cf = cf + 1
				for i in dict[s]:
					if i not in dict[f]:
						cs = cs + 1
				ans = ans + cf * cs * 2
	print(ans)


from collections import defaultdict

def get_common(a, b):
	return len(set(a).intersection(b))
for _ in range(int(input())):
	df = defaultdict(list)
	n = int(input())
	words = list(input().split(' '))
	for word in words:
		df[word[1:]].append(word[0])
	ans = 0
	for key1 in df.keys():
		for key2 in df.keys():
			if key1 != key2:
				common_ele = get_common(df[key1], df[key2])
				ans += (len(df[key1]) - common_ele) * (len(df[key2]) - common_ele)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(str, input().split()))
	c = 0
	s = {}
	k = []
	for i in range(n):
		if l[i][0] in s:
			s[l[i][0]].append(l[i][1:])
		else:
			s[l[i][0]] = [l[i][1:]]
			k.append(l[i][0])
	for i in range(len(k)):
		for j in range(i + 1, len(k)):
			a = len(set(s[k[i]] + s[k[j]]))
			c = c + 2 * (a - len(s[k[i]])) * (a - len(s[k[j]]))
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(str, input().split()))
	d = dict()
	for i in range(N):
		if A[i][1:] in d.keys():
			d[A[i][1:]][ord(A[i][0]) - 97] = 1
		else:
			d[A[i][1:]] = [0 for i in range(26)]
			d[A[i][1:]][ord(A[i][0]) - 97] = 1
	s = 0
	l = []
	for i in d.keys():
		l.append(i)
	for i in range(len(l)):
		for j in range(len(l)):
			a = 0
			b = 0
			for k in range(26):
				if d[l[i]][k] != d[l[j]][k]:
					if d[l[i]][k] == 1:
						a += 1
					else:
						b += 1
			s += a * b
	print(s)


from collections import defaultdict
for test_case in range(int(input())):
	n = int(input())
	output = 0
	inputStrings = [x for x in input().split()]
	Dict = defaultdict(list)
	for x in range(len(inputStrings)):
		Dict[inputStrings[x][0]].append(inputStrings[x][slice(1, len(inputStrings[x]))])
	for i in range(26):
		x = chr(i + 97)
		if Dict.get(x) != None:
			for j in range(i + 1, 26):
				y = chr(j + 97)
				if Dict.get(y) != None:
					(s1, s2) = (Dict[x], Dict[y])
					(first, second) = (len(s1), len(s2))
					for element in s1:
						if element in s2:
							first = first - 1
							second = second - 1
					output += first * second
	print(2 * output)


q = int(input())
for i in range(q):
	n = int(input())
	arr = set(map(str, input().split()))
	temp = set(map(lambda string: string[1:], arr))
	dictionary = {}
	for i in temp:
		dictionary[i] = []
	for i in arr:
		dictionary[i[1:]].append(i[:1])
	count = 0
	for i in dictionary:
		for j in dictionary:
			common = len(set(dictionary[i]).intersection(set(dictionary[j])))
			count += (len(dictionary[i]) - common) * (len(dictionary[j]) - common)
	print(count)


for _ in range(int(input())):
	_ = input()
	a = input().split()
	f = dict()
	for x in range(len(a)):
		if a[x][0] not in f:
			f[a[x][0]] = {a[x][1:]}
		else:
			f[a[x][0]].add(a[x][1:])
	sm = 0
	for x in f:
		for v in f:
			if f[x].difference(f[v]):
				sm += len(f[x].difference(f[v])) * len(f[v].difference(f[x]))
	print(sm)


def check(p1, p2):
	s1 = set(d[p1])
	s2 = set(d[p2])
	c = len(s1 & s2)
	return c
t = int(input(''))
for _ in range(t):
	n = int(input(''))
	s = [item for item in input('').split()]
	d = {}
	for item in s:
		if item[1:] not in d:
			d[item[1:]] = [item[0]]
		else:
			d[item[1:]] = d[item[1:]] + [item[0]]
	ans = 0
	for p1 in d:
		for p2 in d:
			if p1 != p2:
				c = check(p1, p2)
				ans = ans + int((len(d[p1]) - c) * (len(d[p2]) - c))
	print(ans)


from collections import defaultdict

def read_string_array():
	return input().strip().split(' ')

def read_int_array():
	return [int(s) for s in read_string_array()]
DEBUG = False

def solvebf(ws):
	words = set(ws)
	ans = 0
	for x in words:
		for y in words:
			if x == y:
				continue
			xi = x[0]
			yi = y[0]
			xsuff = x[1:]
			ysuff = y[1:]
			w1 = xi + ysuff
			w2 = yi + xsuff
			if xi != yi and xsuff != ysuff and (w1 not in words) and (w2 not in words):
				if DEBUG:
					print(x, y)
				ans += 1
	return ans

def solve(ws):
	by_suffix = defaultdict(set)
	for w in ws:
		l = w[0]
		suff = w[1:]
		by_suffix[suff].add(l)
	ans = 0
	for (suf1, ls1) in by_suffix.items():
		for (suf2, ls2) in by_suffix.items():
			if suf1 >= suf2:
				continue
			common = len(ls1 & ls2)
			good_combinations = (len(ls1) - common) * (len(ls2) - common)
			ans += 2 * good_combinations
	return ans
from random import randint

def randletter():
	return chr(randint(ord('a'), ord('z')))

def randword():
	return ''.join([randletter() for _ in range(randint(2, 3))])

def randomtests(n=1000):
	for _ in range(n):
		testcase = [randword() for _ in range(5)]
		s = solve(testcase)
		b = solvebf(testcase)
		if s != b:
			print(testcase, s, b)
for _ in range(int(input())):
	input()
	print(solve(read_string_array()))


from collections import defaultdict
t = int(input())
for x in range(t):
	n = int(input())
	a = list(input().split())
	c = 0
	d = defaultdict(lambda : set({}))
	for i in range(n):
		d[a[i][1:]].add(a[i][0])
	res = 0
	for i in d:
		for j in d:
			if i != j:
				common = d[i].intersection(d[j])
				res += (len(d[i]) - len(common)) * (len(d[j]) - len(common))
	print(res)


t = int(input())
for tests in range(t):
	n = int(input())
	words = input().split(' ')
	first_char = set([])
	rest_str = {}
	for w in words:
		first_char.add(w[0])
		try:
			rest_str[w[1:]].add(w[0])
		except:
			rest_str[w[1:]] = set([])
			rest_str[w[1:]].add(w[0])
	ans = 0
	for x in rest_str.keys():
		for y in rest_str.keys():
			if not x.__eq__(y):
				l1 = first_char - rest_str.get(x)
				l2 = first_char - rest_str.get(y)
				c1 = len(set(l1) & rest_str.get(y))
				c2 = len(set(l2) & rest_str.get(x))
				ans += c1 * c2
	print(ans)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	words = input().split(' ')
	suffix_map = {}
	answer = 0
	for word in words:
		prefix = word[0:1]
		suffix = word[1:]
		if suffix not in suffix_map:
			suffix_map[suffix] = set()
		suffix_map[suffix].add(prefix)
	for keyI in suffix_map:
		for keyJ in suffix_map:
			if keyI != keyJ:
				answer += len(suffix_map[keyI].difference(suffix_map[keyJ])) * len(suffix_map[keyJ].difference(suffix_map[keyI]))
	print(answer)


ipt = lambda : input()
tests = lambda : range(int(ipt()))
sl = lambda : ipt().split()
il = lambda : list(map(int, sl()))

def mi(m, k):
	m[k] = m.get(k, 0) + 1
for t in tests():
	m = {}
	ipt()
	l = sl()
	for i in l:
		(a, b) = (i[1:], i[0])
		x = m[a] = m.get(a, [])
		x.append(b)
	c = 0
	for i in m:
		for j in m:
			if i != j:
				s = len(set(m[j]) & set(m[i]))
				c += (len(m[j]) - s) * (len(m[i]) - s)
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(input().split())
	ls = {}
	for i in l:
		x = i[1:]
		if x in ls:
			ls[x].append(i[0])
		else:
			ls[x] = [i[0]]
	key = list(ls.keys())
	c = 0
	for i in range(len(ls)):
		for j in range(i + 1, len(ls)):
			x = len(set(ls[key[i]] + ls[key[j]]))
			c = c + (x - len(ls[key[i]])) * (x - len(ls[key[j]]))
	print(2 * c)


import numpy as np
for _ in range(int(input())):
	n = int(input())
	l = list(input().split())
	dic = {'a': [0], 'b': [0], 'c': [0], 'd': [0], 'e': [0], 'f': [0], 'g': [0], 'h': [0], 'i': [0], 'j': [0], 'k': [0], 'l': [0], 'm': [0], 'n': [0], 'o': [0], 'p': [0], 'q': [0], 'r': [0], 's': [0], 't': [0], 'u': [0], 'v': [0], 'w': [0], 'x': [0], 'y': [0], 'z': [0]}
	for k in l:
		a = k[0]
		dic[a].append(k[1:])
		dic[a][0] += 1
	alphabet = 'abcdefghijklmnopqrstuvwxyz'
	(commun, c) = (0, 0)
	for x in range(25):
		X = alphabet[x]
		if dic[X] == [0]:
			continue
		for y in range(x + 1, 26):
			Y = alphabet[y]
			if dic[Y] == [0]:
				continue
			commun = len(set(dic[X][1:] + dic[Y][1:]))
			c += (commun - dic[X][0]) * (commun - dic[Y][0])
	print(2 * c)


for _ in range(int(input())):
	n = int(input())
	l = input().split()
	d = {}
	for i in l:
		if i[1:] not in d.keys():
			d[i[1:]] = [i[0]]
		else:
			d[i[1:]].append(i[0])
	key = [item for item in d.keys()]
	pair = 0
	for i in range(len(key)):
		for j in range(i + 1, len(key)):
			common = len(set(d[key[i]]) & set(d[key[j]]))
			pair += 2 * (len(set(d[key[i]])) - common) * (len(set(d[key[j]])) - common)
	print(pair)


def distinct_length(l1, l2):
	s = len(set(l1 + l2))
	return s
for t in range(int(input())):
	n = int(input())
	funny = input().split()
	words = {}
	for i in funny:
		p = i[1:]
		if p in words:
			words[p].append(i[0])
		else:
			words[p] = [i[0]]
	body = list(words.keys())
	s = 0
	for i in range(len(words)):
		for j in range(i + 1, len(words)):
			temp = distinct_length(words[body[i]], words[body[j]])
			t1 = temp - len(words[body[i]])
			t2 = temp - len(words[body[j]])
			s += t1 * t2
	print(2 * s)


from collections import defaultdict
for test in range(int(input())):
	n = int(input())
	funny = input().split()
	headtail = defaultdict(set)
	for word in funny:
		headtail[word[0]].add(word[1:])
	heads = list(headtail.keys())
	result = 0
	for i in range(len(heads)):
		for j in range(i + 1, len(heads)):
			intersect = len(headtail[heads[i]] & headtail[heads[j]])
			result += 2 * (len(headtail[heads[i]]) - intersect) * (len(headtail[heads[j]]) - intersect)
	print(result)


T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	words = input().strip().split()
	words_dic = dict()
	for word in words:
		if word[0] in words_dic.keys():
			words_dic[word[0]].add(word[1:])
		else:
			words_dic[word[0]] = {word[1:]}
	key_list = list(words_dic.keys())
	ans = 0
	for i in range(len(key_list)):
		for j in range(i + 1, len(key_list)):
			x = len(words_dic[key_list[i]] & words_dic[key_list[j]])
			ans += (len(words_dic[key_list[i]]) - x) * (len(words_dic[key_list[j]]) - x)
	print(ans * 2)


def main():
	t = int(input())
	for z in range(t):
		n = int(input())
		arr = set([x for x in input().split(' ')])
		my_map = dict()
		for word in arr:
			if word[1:] not in my_map:
				my_map[word[1:]] = set(word[0])
			else:
				my_map[word[1:]].add(word[0])
		map_keys = list(my_map.keys())
		ans = 0
		for i in range(len(map_keys)):
			for j in range(i + 1, len(map_keys)):
				common = my_map[map_keys[i]].intersection(my_map[map_keys[j]])
				ans += (len(my_map[map_keys[i]]) - len(common)) * (len(my_map[map_keys[j]]) - len(common))
		print(ans * 2)
main()


from collections import defaultdict

def find(a, b):
	c = 0
	d = 0
	a1 = [0 for i in range(26)]
	b1 = [0 for i in range(26)]
	for i in a:
		a1[ord(i) - 97] = 1
	for i in b:
		b1[ord(i) - 97] = 1
	for i in range(26):
		c = c + a1[i] * (1 - b1[i])
		d = d + b1[i] * (1 - a1[i])
	return c * d * 2

def func(s):
	d = defaultdict(lambda : [])
	ans = 0
	for x in s:
		d[x[1:]].append(x[0])
	key = list(d.keys())
	for i in range(len(d) - 1):
		for j in range(i + 1, len(d)):
			ans += find(d[key[i]], d[key[j]])
	return ans
T = int(input())
for i in range(T):
	n = int(input())
	s = input().split()
	print(func(s))


for i in range(int(input())):
	n = int(input())
	s = input().split()
	d = {}
	for k in s:
		if k[1:] in d:
			d[k[1:]].append(k[0])
		else:
			d[k[1:]] = [k[0]]
	ans = 0
	for i in d:
		for j in d:
			if i != j:
				common = len(set(d[i]) & set(d[j]))
				ans += (len(d[i]) - common) * (len(d[j]) - common)
	print(ans)


def common(str1, str2):
	return len(set(str1 + str2))
for _ in range(int(input())):
	n = int(input())
	names = input().split()
	D = dict()
	for i in names:
		if i[1:] in D:
			D[i[1:]].append(i[0])
		else:
			D[i[1:]] = [i[0]]
	count = 0
	keys = list(D.keys())
	for i in range(len(keys)):
		for j in range(i + 1, len(keys)):
			s1 = D[keys[i]]
			s2 = D[keys[j]]
			com = common(s1, s2)
			count += (len(s1) - com) * (len(s2) - com)
	print(2 * count)


def team_name(arr):
	h = {}
	for x in arr:
		if x[1:] in h:
			h[x[1:]].add(x[0])
		else:
			h[x[1:]] = {x[0]}
	ans = 0
	for w1 in h:
		for w2 in h:
			if w1 != w2:
				i = len(h[w1] & h[w2])
				ans += (len(h[w1]) - i) * (len(h[w2]) - i)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(str, input().split()))
	print(team_name(arr))


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	words = sys.stdin.readline().strip('\n').split()
	ans = 0
	keys = {}
	for i in words:
		if i[0] in keys:
			keys[i[0]].append(i[1:])
		else:
			keys[i[0]] = [i[1:]]
	for (i, start) in enumerate(keys.keys()):
		for j in list(keys.keys())[i + 1:]:
			distinct = len(set(keys[start] + keys[j]))
			ans += (distinct - len(keys[start])) * (distinct - len(keys[j]))
	print(ans * 2)


def commoncount(a, b):
	a_s = set(a)
	b_s = set(b)
	if a_s & b_s:
		return len(a_s & b_s)
	else:
		return 0
t = int(input())
for i in range(t):
	n = int(input())
	names = input().split(' ')
	d = {}
	for name in names:
		if name[1:] in d:
			d[name[1:]].append(name[0])
		else:
			d[name[1:]] = [name[0]]
	total = 0
	for i in d:
		for j in d:
			if i != j:
				common = commoncount(d[i], d[j])
				total += (len(d[i]) - common) * (len(d[j]) - common)
	print(total)


def bre(l):
	dic = {}
	for item in l:
		if item[1:] in dic:
			dic[item[1:]].append(item[0])
		else:
			dic.update({item[1:]: [item[0]]})
	return dic

def check(dic):
	count = 0
	testdic = dic.copy()
	for item1 in dic:
		list1 = dic[item1]
		testdic.pop(item1)
		for item2 in testdic:
			list2 = testdic[item2]
			com = set(list1 + list2)
			t = len(list1) + len(list2) - len(com)
			count += (len(list1) - t) * (len(list2) - t)
	return count
for i in range(int(input())):
	n = int(input())
	a = input().split()
	dictio = bre(a)
	ans = check(dictio)
	print(2 * ans)


def solve():
	pre_map = {}
	alphabets = []
	for s in S:
		pre = s[0]
		if pre not in pre_map:
			pre_map[pre] = set()
			alphabets.append(ord(pre))
		pre_map[pre].add(s[1:])
	ans = 0
	for (ii, i) in enumerate(alphabets):
		for j in alphabets[ii + 1:]:
			common = len(pre_map[chr(i)].intersection(pre_map[chr(j)]))
			ans += (len(pre_map[chr(i)]) - common) * (len(pre_map[chr(j)]) - common)
	return ans * 2
for _ in range(int(input())):
	N = int(input())
	S = [x for x in input().split()]
	print(solve())


def solve():
	pre_map = {chr(x): set() for x in range(ord('a'), ord('z') + 1)}
	for s in S:
		pre_map[s[0]].add(s[1:])
	ans = 0
	for ch1 in range(ord('a'), ord('z') + 1):
		for ch2 in range(ch1 + 1, ord('z') + 1):
			intersection = len(pre_map[chr(ch1)].intersection(pre_map[chr(ch2)]))
			ans += (len(pre_map[chr(ch1)]) - intersection) * (len(pre_map[chr(ch2)]) - intersection)
	return ans * 2
for _ in range(int(input())):
	N = int(input())
	S = [x for x in input().split()]
	print(solve())


for _ in range(int(input())):
	n = int(input())
	l = input().split()
	count = 0
	se = set()
	ans = []
	for i in l:
		se.add(i[0])
	c = set(l)
	for i in l:
		for j in se:
			if j[0] + i[1:] not in c and j[0] + i[1:] not in ans:
				ans.append(j[0] + i[1:])
	if len(ans) > len(l):
		for i in range(n - 1):
			for j in range(i + 1, n):
				if l[i][0] != l[j][0]:
					if l[j][0] + l[i][1:] not in c and l[i][0] + l[j][1:] not in c:
						count += 2
		print(count)
	else:
		for i in range(len(ans) - 1):
			for j in range(i + 1, len(ans)):
				if ans[i][0] != ans[j][0]:
					if ans[i][0] + ans[j][1:] in c and ans[j][0] + ans[i][1:] in c:
						count += 2
		print(count)