Given $n$ strings, each of length $2$, consisting of lowercase Latin alphabet letters from 'a' to 'k', output the number of pairs of indices $(i, j)$ such that $i < j$ and the $i$-th string and the $j$-th string differ in exactly one position.

In other words, count the number of pairs $(i, j)$ ($i < j$) such that the $i$-th string and the $j$-th string have exactly one position $p$ ($1 \leq p \leq 2$) such that ${s_{i}}_{p} \neq {s_{j}}_{p}$.

The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long long in C++ to avoid integer overflow.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of strings.

Then follows $n$ lines, the $i$-th of which containing a single string $s_i$ of length $2$, consisting of lowercase Latin letters from 'a' to 'k'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print a single integer — the number of pairs $(i, j)$ ($i < j$) such that the $i$-th string and the $j$-th string have exactly one position $p$ ($1 \leq p \leq 2$) such that ${s_{i}}_{p} \neq {s_{j}}_{p}$.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).


-----Examples-----

Input
4
6
ab
cb
db
aa
cc
ef
7
aa
bb
cc
ac
ca
bb
aa
4
kk
kk
ab
ab
5
jf
jf
jk
jk
jk
Output
5
6
0
6


-----Note-----

For the first test case the pairs that differ in exactly one position are: ("ab", "cb"), ("ab", "db"), ("ab", "aa"), ("cb", "db") and ("cb", "cc").

For the second test case the pairs that differ in exactly one position are: ("aa", "ac"), ("aa", "ca"), ("cc", "ac"), ("cc", "ca"), ("ac", "aa") and ("ca", "aa").

For the third test case, the are no pairs satisfying the conditions.

Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
from sys import stdin, stdout
import io
import math
import heapq
import bisect
import collections

def ceil(a, b):
	return (a + b - 1) // b
inf = float('inf')

def get():
	return stdin.readline().rstrip()
mod = 10 ** 5 + 7
for _ in range(int(get())):
	n = int(get())
	d1 = defaultdict(int)
	d2 = defaultdict(int)
	ans = 0
	l = []
	for i in range(n):
		s = get()
		d1[s[0]] += 1
		d2[s[1]] += 1
		l.append(s)
	c = Counter(l)
	for i in c:
		ans += (d1[i[0]] - c[i]) * c[i]
		ans += (d2[i[1]] - c[i]) * c[i]
	print(ans // 2)


from collections import defaultdict
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	prefix = defaultdict(int)
	suffix = defaultdict(int)
	entire = defaultdict(int)
	answer = 0
	for __ in range(n):
		temp = input().strip()
		a = temp[0]
		b = temp[1]
		prefix[a] += 1
		suffix[b] += 1
		entire[temp] += 1
	for (k, v) in prefix.items():
		answer += v * (v - 1) // 2
	for (k, v) in suffix.items():
		answer += v * (v - 1) // 2
	for (k, v) in entire.items():
		answer -= v * (v - 1)
	print(answer)


for _ in range(int(input())):
	n = int(input())
	d1 = {}
	d2 = {}
	d3 = {}
	for t in range(n):
		s = input()
		if s in d1:
			d1[s] += 1
		else:
			d1[s] = 1
			if s[0] in d2:
				d2[s[0]] += [s]
			else:
				d2[s[0]] = [s]
			if s[1] in d3:
				d3[s[1]] += [s]
			else:
				d3[s[1]] = [s]
	co = 0
	for i in d2:
		l = d2[i]
		l = [d1[j] for j in l]
		co += (sum(l) ** 2 - sum([j ** 2 for j in l])) // 2
	for i in d3:
		l = d3[i]
		l = [d1[j] for j in l]
		co += (sum(l) ** 2 - sum([j ** 2 for j in l])) // 2
	print(co)


def main():
	n = int(input())
	graph = [[0] * 11 for i in range(11)]
	for i in range(n):
		s = input()
		graph[ord(s[0]) - 97][ord(s[1]) - 97] += 1
	(stroki, stolb) = ([0] * 11, [0] * 11)
	for i in range(11):
		for j in range(11):
			stroki[i] += graph[i][j]
			stolb[j] += graph[i][j]
	ans = 0
	for i in range(11):
		for j in range(11):
			ans += graph[i][j] * (stroki[i] - graph[i][j] + stolb[j] - graph[i][j])
	print(ans // 2)
for i in range(int(input())):
	main()


import sys
from collections import defaultdict

def solution(seq):
	res = 0
	first = defaultdict(int)
	second = defaultdict(int)
	uniq = defaultdict(int)
	for i in seq:
		res += first[i[0]] - uniq[i]
		res += second[i[1]] - uniq[i]
		first[i[0]] += 1
		second[i[1]] += 1
		uniq[i] += 1
	return res
inp = [line.strip() for line in sys.stdin]
i = 1
while i < len(inp):
	cnt = int(inp[i])
	print(solution(inp[i + 1:i + cnt + 1]))
	i = i + cnt + 1


for _ in range(int(input())):
	n = int(input())
	a = [[0 for _ in range(11)] for _ in range(11)]
	ans = 0
	for i in range(n):
		temp = input()
		a[ord(temp[0]) - 97][ord(temp[1]) - 97] += 1
	temp = 0
	for i in range(11):
		temp = 0
		for j in range(11):
			ans -= a[i][j] ** 2
			temp += a[i][j]
		ans += temp ** 2
	for i in range(11):
		temp = 0
		for j in range(11):
			ans -= a[j][i] ** 2
			temp += a[j][i]
		ans += temp ** 2
	print(ans // 2)


for t in range(int(input())):
	ans = 0
	n = int(input())
	dic = {}
	for i in range(1, 12):
		for j in range(1, 12):
			dic[100 * i + j] = 0
	for i in range(n):
		x = input()
		dic[100 * ord(x[0]) + ord(x[1]) - 96 - 9600] += 1
	for i in range(1, 12):
		sum = 0
		for j in range(1, 12):
			sum += dic[100 * i + j]
		ans += sum ** 2
	for i in range(1, 12):
		sum = 0
		for j in range(1, 12):
			sum += dic[100 * j + i]
		ans += sum ** 2
	for (i, j) in dic.items():
		ans -= 2 * j ** 2
	print(ans // 2)


import sys
from string import ascii_lowercase as alp
input = sys.stdin.readline

def count(a):
	d = {}
	for c1 in alp:
		for c2 in alp:
			d[c1, c2] = 0
	for s in a:
		d[s[0], s[1]] += 1
	res = 0
	for c1 in alp:
		total = sum([d[c1, x] for x in alp])
		for c2 in alp:
			cur = d[c1, c2]
			res += cur * (total - cur)
	return res

def solve():
	n = int(input())
	a = []
	for _ in range(n):
		a.append(input().replace('\n', ''))
	print((count(a) + count([x[::-1] for x in a])) // 2)
tst = int(input())
for tt in range(tst):
	solve()


import math

def solve():
	n = int(input())
	d = dict()
	first = dict()
	second = dict()
	arr = []
	for i in range(n):
		a = input()
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
		if a[0] in first:
			first[a[0]] += 1
		else:
			first[a[0]] = 1
		if a[1] in second:
			second[a[1]] += 1
		else:
			second[a[1]] = 1
	ans = 0
	for x in d:
		ans += d[x] * (first[x[0]] - d[x])
		ans += d[x] * (second[x[1]] - d[x])
		first[x[0]] -= d[x]
		second[x[1]] -= d[x]
	print(ans)
t = int(input())
for i in range(t):
	solve()


def solve():
	s = {}
	f = {}
	mp = {}
	for _ in range(int(input())):
		a = input()
		mp[a] = mp.get(a, 0) + 1
		s[a[0]] = s.get(a[0], 0) + 1
		f[a[1]] = f.get(a[1], 0) + 1
	ans = 0
	for (a, i) in mp.items():
		ans += i * (s[a[0]] - i) + i * (f[a[1]] - i)
	print(ans // 2)
t = int(input())
for i in range(t):
	solve()


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input().strip())
	dic = defaultdict(int)
	for i in range(n):
		temp = input().strip()
		dic[temp] += 1
	brr = []
	ans = 0
	for i in range(11):
		brr.append(chr(97 + i))
	for ele in brr:
		hor1 = []
		for st_e in dic.keys():
			if st_e[0] == ele:
				hor1.append(dic[st_e])
		l1 = len(hor1)
		for r in range(l1 - 1):
			for z in range(r + 1, l1):
				ans += hor1[r] * hor1[z]
		hor2 = []
		for st_e in dic.keys():
			if st_e[1] == ele:
				hor2.append(dic[st_e])
		l2 = len(hor2)
		for r in range(l2 - 1):
			for z in range(r + 1, l2):
				ans += hor2[r] * hor2[z]
	print(ans)


for tcase in range(int(input())):
	a = [[0] * 11 for i in range(11)]
	for _ in range(int(input())):
		s = input()
		i = ord(s[0]) - ord('a')
		j = ord(s[1]) - ord('a')
		a[i][j] += 1
	(r, c) = ([0] * 11, [0] * 11)
	for i in range(11):
		for j in range(11):
			r[i] += a[i][j]
			c[j] += a[i][j]
	ans = 0
	for i in range(11):
		for j in range(11):
			ans += a[i][j] * (r[i] + c[j] - 2 * a[i][j])
	print(ans // 2)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	ar = []
	temp = []
	for x in range(15):
		temp = []
		for y in range(15):
			temp.append(0)
		ar.append(temp)
	ans = 0
	for x in range(n):
		ch = input()
		a = ord(ch[0]) - 97
		b = ord(ch[1]) - 97
		ar[a][b] += 1
	for x in range(15):
		s = 0
		for y in range(15):
			if ar[x][y] > 1:
				ans -= math.comb(ar[x][y], 2)
			s += ar[x][y]
		ans += math.comb(s, 2)
	for x in range(15):
		s = 0
		for y in range(15):
			if ar[y][x] > 1:
				ans -= math.comb(ar[y][x], 2)
			s += ar[y][x]
		ans += math.comb(s, 2)
	print(ans)


T = int(input())
from collections import defaultdict, Counter
from math import comb
for _ in range(T):
	l = int(input())
	(f_dict, s_dict) = (defaultdict(list), defaultdict(list))
	st = []
	for _ in range(l):
		s = input()
		st.append(s)
		f_dict[s[0]].append(s)
		s_dict[s[1]].append(s)
	cnt = 0
	for v in f_dict.values():
		if len(v) >= 2:
			cnt += comb(len(v), 2)
	for v in s_dict.values():
		if len(v) >= 2:
			cnt += comb(len(v), 2)
	c = Counter(st)
	for v in c.values():
		if v >= 2:
			cnt -= comb(v, 2) * 2
	print(cnt)


t = int(input())
for k in range(t):
	n = int(input())
	letters = 'abcdefghijk'
	db = {c: {h: 0 for h in letters} for c in letters}
	de = {h: {c: 0 for c in letters} for h in letters}
	ans = 0
	for p in range(n):
		s = input()
		(c, h) = (s[0], s[1])
		db[c][h] += 1
		de[h][c] += 1
	for c in letters:
		for h in db[c]:
			ans += db[c][h] * sum([db[c][other] for other in db[c] if other != h])
			db[c][h] = 0
	for h in letters:
		for c in de[h]:
			if c != h:
				ans += de[h][c] * sum([de[h][other] for other in de[h] if other != c])
				de[h][c] = 0
	print(ans)


from math import comb
T = int(input())

def solve(l):
	cnt = 0
	st_d = {}
	ed_d = {}
	same_d = {}
	for c in l:
		if c[0] in st_d:
			st_d[c[0]] += 1
		else:
			st_d[c[0]] = 1
		if c[1] in ed_d:
			ed_d[c[1]] += 1
		else:
			ed_d[c[1]] = 1
		if c in same_d:
			same_d[c] += 1
		else:
			same_d[c] = 1
	for key in st_d.keys():
		if st_d[key] == 1:
			continue
		else:
			cnt += comb(st_d[key], 2)
	for key in ed_d.keys():
		if ed_d[key] == 1:
			continue
		else:
			cnt += comb(ed_d[key], 2)
	for key in same_d.keys():
		if same_d[key] == 1:
			continue
		else:
			cnt -= 2 * comb(same_d[key], 2)
	return cnt
for _ in range(T):
	N = int(input())
	l = [input() for _ in range(N)]
	print(solve(l))


import fileinput

def getanswer(strings):
	counts = {}
	for string in strings:
		counts[string] = counts.get(string, 0) + 1
	matches = 0
	unique_strings_present = list(counts.keys())
	for string in unique_strings_present[:-1]:
		num = counts[string]
		multiplier = 0
		for char in ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']:
			multiplier += counts.get(string[0] + char, 0) + counts.get(char + string[1], 0)
		matches += num * (multiplier - 2 * num)
		counts[string] = 0
	return matches

def solve():
	ins = []
	for line in fileinput.input():
		ins.append(line.strip('\n'))
	num_tests = int(ins[0])
	j = 1
	for i in range(num_tests):
		num_strings = int(ins[j])
		strings = ins[j + 1:j + num_strings + 1]
		j += num_strings + 1
		c = getanswer(strings)
		print(c)
solve()


from random import getrandbits
RANDOM = getrandbits(32)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM
T = int(input())
q = []
for i in range(T):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(input())
	q.append((arr, n))
target = 'abcdefghijk'

def solve(arr, n):
	dist = dict()
	for a in target:
		for b in target:
			dist[a + b] = 0
	for a in arr:
		dist[a] += 1
	ans = 0
	for key in dist:
		if dist[key] > 0:
			left = ord(key[0]) - ord('a')
			for i in range(left + 1, 11):
				ans += dist[target[i] + key[1]] * dist[key]
			right = ord(key[1]) - ord('a')
			for i in range(right + 1, 11):
				ans += dist[key[0] + target[i]] * dist[key]
	print(ans)
for (arr, n) in q:
	solve(arr, n)


t = int(input())
for i in range(t):
	lst1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
	lst2 = []
	for j in lst1:
		s1 = j
		lst3 = []
		for k in lst1:
			s1 += k
			lst3.append(s1)
			s1 = j
		lst2.append(lst3)
	for j in lst1:
		s1 = j
		lst3 = []
		for k in lst1:
			s1 = k + s1
			lst3.append(s1)
			s1 = j
		lst2.append(lst3)
	dic = {}
	for j in lst2:
		for k in j:
			dic[k] = 0
	n = int(input())
	lst = []
	for j in range(n):
		s = input()
		lst.append(s)
	for j in lst:
		dic[j] += 1
	c = 0
	l = 11
	for j in lst2:
		for k in range(11):
			for f in range(k + 1, 11):
				a = dic[j[k]]
				b = dic[j[f]]
				c += a * b
	print(c)


from collections import Counter

def main():
	n = int(input())
	words = []
	for i in range(n):
		s = input()
		words.append(s)
	freq = Counter(words)
	f = {}
	l = {}
	for z in words:
		al = z[0]
		if al not in f:
			f[al] = 0
		f[al] += 1
	for z in words:
		al = z[1]
		if al not in l:
			l[al] = 0
		l[al] += 1
	ans = 0
	for (k, v) in f.items():
		ans += v * (v - 1) // 2
	for (k, v) in l.items():
		ans += v * (v - 1) // 2
	for (k, v) in freq.items():
		ans -= v * (v - 1)
	return ans
for _ in range(int(input())):
	print(main())


a = 'abcdefghijk'
l = []
for i in range(11):
	for j in range(11):
		l.append(a[i] + a[j])
w = []
for i in range(len(l)):
	p = []
	for j in range(len(l)):
		if (l[i][0] == l[j][0]) ^ (l[i][1] == l[j][1]):
			p.append(j)
	w.append(tuple(p))
for _ in range(int(input())):
	dic = {}
	for i in l:
		dic[i] = 0
	for i in range(int(input())):
		dic[input()] += 1
	ans = 0
	for i in range(len(w)):
		for j in w[i]:
			ans += dic[l[i]] * dic[l[j]]
	print(ans // 2)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	d = defaultdict(int)
	f = defaultdict(int)
	sec = defaultdict(int)
	s = set([])
	for i in range(n):
		x = input().strip()
		d[x] += 1
		f[x[0]] += 1
		sec[x[1]] += 1
		s.add(x)
	ans = 0
	for i in 'abcdefghijk':
		ans += f[i] * (f[i] - 1) // 2
		ans += sec[i] * (sec[i] - 1) // 2
	for i in s:
		ans -= d[i] * (d[i] - 1)
	print(ans)


def compute(dictionary, first_letter_dict, second_letter_dict):
	tmp_inc = 0
	tmp_dec = 0
	for first in first_letter_dict:
		tmp_inc += first_letter_dict[first] * (first_letter_dict[first] - 1) / 2
	for second in second_letter_dict:
		tmp_inc += second_letter_dict[second] * (second_letter_dict[second] - 1) / 2
	for vocab in dictionary:
		tmp_dec += dictionary[vocab] * (dictionary[vocab] - 1)
	return int(tmp_inc - tmp_dec)
count_of_test = int(input())
for _ in range(count_of_test):
	length_of_arr = int(input())
	dictionary = {}
	first_letter_dict = {}
	second_letter_dict = {}
	for j in range(length_of_arr):
		item = input()
		if item not in dictionary:
			dictionary[item] = 0
		dictionary[item] += 1
		first_letter = item[0]
		second_letter = item[1]
		if first_letter not in first_letter_dict:
			first_letter_dict[first_letter] = 0
		first_letter_dict[first_letter] += 1
		if second_letter not in second_letter_dict:
			second_letter_dict[second_letter] = 0
		second_letter_dict[second_letter] += 1
	print(compute(dictionary, first_letter_dict, second_letter_dict))


import sys
getline = sys.stdin.readline

def read_int():
	return int(getline())

def read_ints():
	return list(map(int, getline().split()))

def read_s():
	return str(getline().strip())

def read_ss():
	return list(map(str, getline().strip().split()))
from collections import defaultdict
t = read_int()
for _ in range(t):
	n = read_int()
	starts = defaultdict(int)
	ends = defaultdict(int)
	dups = defaultdict(int)
	ans = 0
	for line in range(n):
		s = read_s()
		p = s[0]
		q = s[1]
		ans += starts[p] + ends[q] - dups[s] * 2
		starts[p] += 1
		ends[q] += 1
		dups[s] += 1
	print(ans)


t = int(input())
for i in range(t):
	matrix = []
	for _ in range(11):
		matrix.append([0] * 11)
	n = int(input())
	my_sum = 0
	for j in range(n):
		new_str = str(input())
		first = ord(new_str[0]) - 97
		second = ord(new_str[1]) - 97
		matrix[first][second] += 1
	for k in range(11):
		for kk in range(11):
			if kk != 10:
				my_sum += matrix[k][kk] * sum(matrix[k][kk + 1:])
			if k != 10:
				my_sum += matrix[k][kk] * sum((matrix[num][kk] for num in range(k + 1, 11)))
	print(my_sum)


from collections import defaultdict, deque
import math
from random import random, shuffle
from sys import setrecursionlimit
import os, sys
cwd = os.getcwd()
if os.path.exists(cwd + '/test/input.txt'):
	sys.stdin = open(cwd + '/test/input.txt', 'r')
	sys.stdout = open(cwd + '/test/output.txt', 'w')
setrecursionlimit(10 ** 6)
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(dx, dy) = ([1, 1, -1, -1], [1, -1, 1, -1])
lowbit = lambda x: x & -x

class BIT:

	def __init__(self, n):
		self.bit = [0] * (n + 1)

	def upd(self, idx, val):
		bit = self.bit
		while idx <= len(bit):
			bit[idx] += val
			idx += lowbit(idx)

	def query(self, idx):
		res = 0
		bit = self.bit
		while idx > 0:
			res += bit[idx]
			idx -= lowbit(idx)
		return res

def solve():
	T = int(input())
	while T:
		T -= 1
		n = int(input())
		(mp1, mp2, mp) = (defaultdict(int), defaultdict(int), defaultdict(int))
		res = 0
		for i in range(n):
			s = input()
			res += mp1[s[0]] + mp2[s[1]] - mp[s] * 2
			mp1[s[0]] += 1
			mp2[s[1]] += 1
			mp[s] += 1
		print(res)
solve()


for _ in range(int(input())):
	d = {}
	n = int(input())
	for q in range(n):
		s = input()
		if s not in d:
			d[s] = 0
		d[s] += 1
	L = d.keys()
	L = sorted(L)
	res = 0
	for i in L:
		beg = ord(i[0]) + 1
		for p in range(beg, 108):
			st = chr(p) + i[1]
			if st in d:
				res += d[i] * d[st]
		beg = ord(i[1]) + 1
		for p in range(beg, 108):
			st = i[0] + chr(p)
			if st in d:
				res += d[i] * d[st]
	print(res)


from collections import defaultdict, Counter
for case in range(int(input())):
	n = int(input())
	arr = [input() for _ in range(n)]
	(left, right) = ('', '')
	for i in arr:
		left += i[0]
		right += i[1]
	(left_c, right_c) = (Counter(left), Counter(right))
	arrCounter = Counter(arr)
	duplicates = sum(((v - 1) * v // 2 for (k, v) in arrCounter.items() if v > 1))
	res = sum(((v - 1) * v // 2 for (k, v) in left_c.items() if v > 1))
	res += sum(((v - 1) * v // 2 for (k, v) in right_c.items() if v > 1))
	res -= duplicates * 2
	print(res)


from collections import defaultdict
for _ in range(int(input())):
	d = defaultdict(int)
	for __ in range(int(input())):
		d[input()] += 1
	ans = 0
	for word in list(d.keys()):
		(first, second) = (word[0], word[1])
		for char in 'abcdefghijk':
			if char != second:
				ans += d[word] * d[first + char]
			if char != first:
				ans += d[word] * d[char + second]
	print(ans // 2)


import sys
input = sys.stdin.readline

def insr():
	s = input()
	return s[:len(s) - 1]

def pair_count(d):
	return sum((i * (i - 1) // 2 for i in d.values()))

def Difference(array, m):
	(changed, same) = ({}, {})
	for s in array:
		same[s] = same.get(s, 0) + 1
		for i in range(m):
			t = s[:i] + '#' + s[i + 1:]
			changed[t] = changed.get(t, 0) + 1
	return pair_count(changed) - pair_count(same) * m
t = int(input())
for _ in range(t):
	n = int(input())
	set_s = []
	for i in range(n):
		set_s.append(insr())
	count = 0
	print(Difference(set_s, 2))


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [[0 for _ in range(11)] for __ in range(11)]
	for _ in range(n):
		s = input()
		x = ord(s[0]) - ord('a')
		y = ord(s[1]) - ord('a')
		a[x][y] += 1
	r = 0
	for i in range(11):
		d = a[i][0]
		for j in range(1, 11):
			r += d * a[i][j]
			d += a[i][j]
		d = a[0][i]
		for j in range(1, 11):
			r += d * a[j][i]
			d += a[j][i]
	print(r)


for _ in range(int(input())):
	start = {}
	end = {}
	g = {}
	for j in range(int(input())):
		a = input()
		if a in g:
			g[a] += 1
		else:
			g[a] = 1
		if a[0] in start:
			start[a[0]] += [a]
		else:
			start[a[0]] = [a]
		if a[1] in end:
			end[a[1]] += [a]
		else:
			end[a[1]] = [a]
	ans = 0
	for item in start:
		a = start[item]
		b = list(set(a))
		cc = 0
		for it in b:
			cache = len(a)
			cache -= g[it]
			cache = cache * g[it]
			cc += cache
		ans += cc // 2
	start = end
	for item in start:
		a = start[item]
		b = list(set(a))
		cc = 0
		for it in b:
			cache = len(a)
			cache -= g[it]
			cache = cache * g[it]
			cc += cache
		ans += cc // 2
	print(ans)


n = input()
for _ in range(int(n)):
	num = int(input())
	Dict = dict()
	arr1 = dict()
	arr2 = dict()
	ans = 0
	for i in range(num):
		str1 = input()
		if str1 in Dict:
			Dict[str1] += 1
		else:
			Dict[str1] = 1
		a = str1[0]
		b = str1[1]
		if a in arr1:
			arr1[a] += 1
		else:
			arr1[a] = 1
		if b in arr2:
			arr2[b] += 1
		else:
			arr2[b] = 1
	for (key, value) in Dict.items():
		(a, b) = (key[0], key[1])
		ans += value * (arr1[a] - value)
		ans += value * (arr2[b] - value)
	print(int(ans / 2))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d1 = defaultdict(int)
	fr = defaultdict(int)
	d2 = defaultdict(int)
	ans = 0
	for i in range(n):
		s = input()
		ans += d1[s[0]] + d2[s[1]] - 2 * fr[s]
		fr[s] += 1
		d1[s[0]] += 1
		d2[s[1]] += 1
	print(ans)


def compute(vocab):
	add = 0
	dec = 0
	for k in vocab.keys():
		if 'first' in k:
			add += vocab[k] * (vocab[k] - 1) / 2
		elif 'second' in k:
			add += vocab[k] * (vocab[k] - 1) / 2
		else:
			dec += vocab[k] * (vocab[k] - 1)
	return int(add - dec)
n = int(input())
for _ in range(n):
	vocab = {}
	m = int(input())
	for i in range(m):
		item = input()
		if item not in vocab:
			vocab[item] = 1
		else:
			vocab[item] += 1
		letter1 = 'first ' + item[0]
		if letter1 not in vocab:
			vocab[letter1] = 1
		else:
			vocab[letter1] += 1
		letter2 = 'second ' + item[1]
		if letter2 not in vocab:
			vocab[letter2] = 1
		else:
			vocab[letter2] += 1
	print(compute(vocab))


size = int(input())
for i in range(size):
	testSize = int(input())
	strings_start = {}
	strings_end = {}
	for j in range(testSize):
		string = input()
		try:
			strings_start[string[0]]
		except:
			strings_start[string[0]] = {string: 0}
		try:
			strings_start[string[0]][string] += 1
		except:
			strings_start[string[0]][string] = 1
		try:
			strings_end[string[1]]
		except:
			strings_end[string[1]] = {string: 0}
		try:
			strings_end[string[1]][string] += 1
		except:
			strings_end[string[1]][string] = 1
	sum = 0
	for ss in strings_start:
		k = list(strings_start[ss].keys())
		for i in range(len(k) - 1):
			for j in range(i + 1, len(k)):
				sum += strings_start[ss][k[i]] * strings_start[ss][k[j]]
	for ss in strings_end:
		k = list(strings_end[ss].keys())
		for i in range(len(k) - 1):
			for j in range(i + 1, len(k)):
				sum += strings_end[ss][k[i]] * strings_end[ss][k[j]]
	print(sum)


for _ in range(int(input())):
	c = [[0] * 11 for _ in range(11)]
	for _ in range(int(input())):
		s = input()
		c[ord(s[0]) - ord('a')][ord(s[1]) - ord('a')] += 1
	ans = 0
	for i in range(11):
		for j in range(11):
			for k in range(j + 1, 11):
				ans += c[i][j] * c[i][k]
				ans += c[j][i] * c[k][i]
	print(ans)


a = 'abcdefghijk'
for t in range(int(input())):
	n = int(input())
	rs = 0
	ms = [[0] * 11 for i in range(11)]
	for i in range(n):
		s = input()
		ms[ord(s[0]) - 97][ord(s[1]) - 97] += 1
	for i in range(11):
		for j in range(11):
			for k in range(11):
				if k != j:
					rs += ms[i][j] * ms[i][k]
				if k != i:
					rs += ms[i][j] * ms[k][j]
	print(rs // 2)


from collections import defaultdict
tc = int(input())
for _ in range(1, tc + 1):
	n = int(input())
	(a, b) = ([], [])
	for i in range(12):
		a.append([0] * 12)
		b.append([0] * 12)
	for i in range(n):
		s = input()
		(row, col) = (ord(s[0]) - 96, ord(s[1]) - 96)
		a[row][col] += 1
		b[col][row] += 1
	c = 0
	for i in range(12):
		for j in range(12):
			for k in range(j + 1, 12):
				c += a[i][j] * a[i][k] + b[i][j] * b[i][k]
	print(c)


from collections import defaultdict
TESTS = int(input())
for _ in range(TESTS):
	l = int(input())

	def init():
		return 0
	strings = defaultdict(init)
	start_strings = defaultdict(init)
	end_strings = defaultdict(init)
	counter = 0
	for _ in range(l):
		s = input()
		(a, b) = s
		counter += start_strings[a] + end_strings[b] - 2 * strings[s]
		strings[s] += 1
		start_strings[a] += 1
		end_strings[b] += 1
	print(counter)


import math as m
i = int(input())
inp = []
for a in range(i):
	n = int(input())
	x = []
	for i in range(n):
		x += [input()]
	inp += [x]
for l in inp:
	ret = 0
	di = {}
	for c in 'abcdefghijk':
		di[c] = {}
		for d in 'abcdefghijk':
			di[c][d] = 0
	for s in l:
		di[s[0]][s[1]] += 1
	for z in range(97, 108):
		c = chr(z)
		for i in range(97, 108):
			for j in range(i + 1, 108):
				ret += di[c][chr(i)] * di[c][chr(j)]
	di = {}
	for c in 'abcdefghijk':
		di[c] = {}
		for d in 'abcdefghijk':
			di[c][d] = 0
	for s in l:
		di[s[1]][s[0]] += 1
	for z in range(97, 108):
		c = chr(z)
		for i in range(97, 108):
			for j in range(i + 1, 108):
				ret += di[c][chr(i)] * di[c][chr(j)]
	print(ret)


from collections import defaultdict as dfd

def solve(array):
	ans = 0
	(book_head, cnt_head) = ({}, dfd(int))
	for i in range(97, 108):
		book_head[chr(i)] = dfd(int)
	(book_tail, cnt_tail) = ({}, dfd(int))
	for i in range(97, 108):
		book_tail[chr(i)] = dfd(int)
	for s in array:
		(h, t) = (s[0], s[1])
		ans += cnt_head[h] - book_head[h][t]
		ans += cnt_tail[t] - book_tail[t][h]
		book_head[h][t] += 1
		cnt_head[h] += 1
		book_tail[t][h] += 1
		cnt_tail[t] += 1
	return ans
T = int(input())
for _ in range(T):
	N = int(input())
	array = []
	for _ in range(N):
		array.append(str(input()))
	print(solve(array))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	(dstart, dend) = (defaultdict(int), defaultdict(int))
	D = defaultdict(int)
	ans = 0
	for i in range(n):
		s = input()
		ans += dstart[s[0]] + dend[s[1]]
		if s in D:
			ans -= 2 * D[s]
		D[s] += 1
		dstart[s[0]] += 1
		dend[s[1]] += 1
	print(ans)


t = int(input())
out = ''
alp = 'abcdefghijk'
for _ in range(t):
	count = {}
	count1 = {}
	count2 = {}
	for l in alp:
		count1[l] = 0
		count2[l] = 0
		for l2 in alp:
			count[l + l2] = 0
	n = int(input())
	ans = 0
	for _ in range(n):
		string = input()
		ans += count1[string[0]] - count[string]
		ans += count2[string[1]] - count[string]
		count1[string[0]] += 1
		count2[string[1]] += 1
		count[string] += 1
	out += str(ans) + '\n'
print(out)


for t in range(int(input())):
	n = int(input())
	was = {}
	(beg, end) = ({}, {})
	ans = 0
	for i in range(n):
		s = input()
		if s not in was:
			was[s] = 0
		if s[0] not in beg:
			beg[s[0]] = 0
		if s[1] not in end:
			end[s[1]] = 0
		ans += beg[s[0]] + end[s[1]] - 2 * was[s]
		was[s] += 1
		beg[s[0]] += 1
		end[s[1]] += 1
	print(ans)


T = int(input())
for case in range(T):
	n = int(input())
	h = {}
	h1 = {}
	h2 = {}
	ans = 0
	for i in range(n):
		x = input()
		(s, t) = tuple(x)
		h.setdefault(x, 0)
		h1.setdefault(s, 0)
		h2.setdefault(t, 0)
		ans += h1[s] + h2[t] - 2 * h[x]
		h[x] += 1
		h1[s] += 1
		h2[t] += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = []
	for i in range(n):
		xyz = input()
		s.append(xyz)
	arr = [[0 for i in range(12)] for i in range(12)]
	for i in range(n):
		x = s[i][0]
		y = s[i][1]
		xi = int(ord(x) - ord('a'))
		yi = int(ord(y) - ord('a'))
		arr[xi][yi] += 1
	rsum = [[0 for i in range(12)] for i in range(12)]
	csum = [[0 for i in range(12)] for i in range(12)]
	for i in range(12):
		cursum = 0
		for j in range(11, -1, -1):
			cursum += arr[i][j]
			rsum[i][j] = cursum
	for j in range(12):
		cursum = 0
		for i in range(11, -1, -1):
			cursum += arr[i][j]
			csum[i][j] = cursum
	ans = 0
	for i in range(12):
		for j in range(11):
			ans += (rsum[i][j] - rsum[i][j + 1]) * rsum[i][j + 1]
	for i in range(12):
		for j in range(11):
			ans += (csum[j][i] - csum[j + 1][i]) * csum[j + 1][i]
	print(ans)


from collections import Counter
from itertools import groupby

def solve():
	n = int(input())
	s = [tuple(input()) for _ in range(n)]
	groups = []
	for (key, val) in groupby(sorted(s, key=lambda x: x[0]), key=lambda x: x[0]):
		groups.append(list(map(lambda x: x[1], val)))
	for (key, val) in groupby(sorted(s, key=lambda x: x[1]), key=lambda x: x[1]):
		groups.append(list(map(lambda x: x[0], val)))
	ans = 0
	for group in groups:
		m = len(group)
		ans += m * (m - 1) // 2
		for k in Counter(group).values():
			ans -= k * (k - 1) // 2
	print(ans)
t = int(input())
for _ in range(t):
	solve()


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for test in range(t):
	n = inp()
	(dic, count) = ({}, 0)
	for i in range(n):
		s = insr()
		(c1, c2, v) = (s[0], s[1], 0)
		if (c1, v) not in dic:
			dic[c1, v] = 0
		if (c1, c2) not in dic:
			dic[c1, c2] = 0
		if (v, c2) not in dic:
			dic[v, c2] = 0
		dic[c1, v] += 1
		dic[c1, c2] += 1
		dic[v, c2] += 1
	for pair in dic:
		(u, v) = (pair[0], pair[1])
		if v == 0 or u == 0:
			count += math.comb(dic[u, v], 2)
		else:
			count -= 2 * math.comb(dic[u, v], 2)
	print(count)


from collections import defaultdict as dict
for _ in ' ' * int(input()):
	d_f = dict(int)
	d_s = dict(int)
	cnt = dict(int)
	ans = 0
	for _ in ' ' * int(input()):
		s = input()
		cnt[s] += 1
		ans += d_f[s[0]] + d_s[s[1]] - 2 * cnt[s] + 2
		d_f[s[0]] += 1
		d_s[s[1]] += 1
	print(ans)


t = int(input())

def val(a):
	return ord(a) - ord('a')
for i in range(t):
	l = []
	n = int(input())
	freq1 = [0] * 121
	freq2 = [0] * 121
	for j in range(n):
		temp = input()
		freq1[val(temp[0]) * 11 + val(temp[1])] += 1
		freq2[val(temp[1]) * 11 + val(temp[0])] += 1
	ans = 0
	for j in range(11):
		total = sum(freq1[j * 11:(j + 1) * 11])
		prev = 0
		for k in freq1[j * 11:(j + 1) * 11]:
			if k != 0:
				ans += (total - k - prev) * k
				prev += k
		total = sum(freq2[j * 11:(j + 1) * 11])
		prev = 0
		for k in freq2[j * 11:(j + 1) * 11]:
			if k != 0:
				ans += (total - k - prev) * k
				prev += k
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	result = 0
	grid = [[0 for _ in range(11)] for _ in range(11)]
	for _ in range(n):
		s = input()
		a = s[0]
		b = s[1]
		grid[ord(a) - ord('a')][ord(b) - ord('a')] += 1
	for i in range(11):
		for j in range(11):
			result += grid[i][j] * sum([grid[k][j] for k in range(11) if k != i])
			result += grid[i][j] * sum([grid[i][k] for k in range(11) if k != j])
	print(result // 2)


from collections import *
I = input
for _ in [0] * int(I()):
	a = Counter((I() for _ in [0] * int(I())))
	b = (*a,)
	print(sum((a[u + v] * a[x + y] for (i, (u, v)) in enumerate(b) for (x, y) in b[:i] if (x == u) ^ (v == y))))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(input())
	s = defaultdict(int)
	e = defaultdict(int)
	d = defaultdict(int)
	for i in arr:
		s[i[0]] += 1
		e[i[1]] += 1
		d[i] += 1
	ans = 0
	for i in arr:
		ans += s[i[0]] - 1 + (e[i[1]] - 1) - 2 * (d[i] - 1)
	print(ans // 2)


a = []
for _ in range(int(input())):
	k = int(input())
	c = 0
	l = {w: 0 for w in 'qwertyuiopasdfghjklzxcvbnm'}
	l1 = {w: 0 for w in 'qwertyuiopasdfghjklzxcvbnm'}
	l2 = dict()
	for i in range(k):
		s = input()
		m = 1
		if s not in l2:
			l2[s] = 0
			m = 0
		c = c + l[s[0]] + l1[s[1]]
		l[s[0]] += 1
		l1[s[1]] += 1
		if m:
			c -= l2[s] * 2
		l2[s] += 1
	a.append(str(c))
print('\n'.join(a))


for _ in range(int(input())):
	n = int(input())
	d = {}
	ans = 0
	for a in range(n):
		s = input()
		try:
			d[s.upper()] += 1
		except:
			d[s.upper()] = 1
	for i in range(11):
		s1 = chr(i + 65)
		for j in range(11):
			s2 = chr(j + 65)
			total = s1 + s2
			if total in d:
				for k in range(j + 1, 11):
					if s1 + chr(k + 65) in d:
						ans += d[s1 + chr(k + 65)] * d[total]
				for k in range(i + 1, 11):
					if chr(k + 65) + s2 in d:
						ans += d[chr(k + 65) + s2] * d[total]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	result = 0
	dic1 = {}
	dic2 = {}
	dic3 = {}
	for i in range(n):
		S = input()
		if S[0] in dic1:
			result += dic1[S[0]]
			dic1[S[0]] += 1
		else:
			dic1[S[0]] = 1
		if S[1] in dic2:
			result += dic2[S[1]]
			dic2[S[1]] += 1
		else:
			dic2[S[1]] = 1
		if S in dic3:
			result -= dic3[S] * 2
			dic3[S] += 1
		else:
			dic3[S] = 1
	print(result)


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
ANS = []
for t in range(int(input())):
	n = int(input())
	a = [input().strip() for i in range(n)]
	start = [0] * 26
	end = [0] * 26
	count = {}
	ans = 0
	for i in a:
		x = start[ord(i[0]) - ord('a')]
		y = end[ord(i[1]) - ord('a')]
		z = 0
		if i in count:
			z = count[i]
		ans += x + y - 2 * z
		if i not in count:
			count[i] = 0
		count[i] += 1
		start[ord(i[0]) - ord('a')] += 1
		end[ord(i[1]) - ord('a')] += 1
	print(ans)


import sys
from collections import defaultdict
for t in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		temp = input()
		a.append(temp)
	mp1 = defaultdict(lambda : 0)
	mp2 = defaultdict(lambda : 0)
	mpchar = defaultdict(lambda : 0)
	mid = 0
	ans = 0
	for i in range(n - 1, -1, -1):
		mid = mp1[a[i][0]] + mp2[a[i][1]] - 2 * mpchar[a[i]]
		ans += mid
		mpchar[a[i]] += 1
		mp1[a[i][0]] += 1
		mp2[a[i][1]] += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	first = {chr(x): [0, dict()] for x in range(97, 108)}
	second = {chr(x): [0, dict()] for x in range(97, 108)}
	for i in range(n):
		word = input()
		first[word[0]][0] += 1
		first[word[0]][1][word[1]] = first[word[0]][1].get(word[1], 0) + 1
		second[word[1]][0] += 1
		second[word[1]][1][word[0]] = second[word[1]][1].get(word[0], 0) + 1
	ans = 0
	for i in range(97, 108):
		for j in range(97, 108):
			ans += first[chr(i)][1].get(chr(j), 0) * (first[chr(i)][0] - first[chr(i)][1].get(chr(j), 0))
			ans += second[chr(i)][1].get(chr(j), 0) * (second[chr(i)][0] - second[chr(i)][1].get(chr(j), 0))
	print(ans // 2)


for _ in range(int(input())):
	n = int(input())
	words = [input() for i in range(n)]
	(letter1, letter2, duplicates) = ({}, {}, {})
	for w in words:
		duplicates[w] = duplicates.get(w, 0) + 1
		letter1[w[0]] = letter1.get(w[0], 0) + 1
		letter2[w[1]] = letter2.get(w[1], 0) + 1
	summ = 0
	for i in range(n):
		word1 = words[i]
		summ += letter1[word1[0]] + letter2[word1[1]] - duplicates[word1] * 2
	print(summ // 2)


T = int(input())
for _ in range(T):
	n = int(input())
	marker = {}
	count0 = []
	count1 = []
	for i in range(11):
		count0.append([])
		count1.append([])
	for i in range(97, 108):
		for j in range(97, 108):
			x = chr(i) + chr(j)
			marker[x] = 0
	for i in range(n):
		s = input()
		marker[s] += 1
	for key in marker:
		first = ord(key[0]) - 97
		second = ord(key[-1]) - 97
		count0[first].append(marker[key])
		count1[second].append(marker[key])
	ans = 0
	for item in count0:
		x = 0
		for i in range(len(item)):
			for j in range(len(item)):
				if i != j:
					x += int(item[i]) * int(item[j])
		ans += x // 2
	for item in count1:
		x = 0
		for i in range(len(item)):
			for j in range(len(item)):
				if i != j:
					x += int(item[i]) * int(item[j])
		ans += x // 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = [input() for _ in range(n)]
	a = [0] * 11
	b = [0] * 11
	c = [0] * (11 * 11)
	ans = 0
	for x in s:
		p = ord(x[0]) - ord('a')
		q = ord(x[1]) - ord('a')
		ans += a[p] + b[q] - c[p * 11 + q] * 2
		a[p] += 1
		b[q] += 1
		c[p * 11 + q] += 1
	print(ans)


for t in range(int(input())):
	number_of_strings = int(input())
	pairs = [input() for i in range(number_of_strings)]
	number_of_diff1_pairs = 0
	first_letters = {}
	last_letters = {}
	full_letters = {}
	for i in range(number_of_strings):
		number_of_diff1_pairs += first_letters.get(pairs[i][0], 0) + last_letters.get(pairs[i][1], 0) - 2 * full_letters.get(pairs[i], 0)
		if pairs[i][0] in first_letters:
			first_letters[pairs[i][0]] += 1
		else:
			first_letters[pairs[i][0]] = 1
		if pairs[i][1] in last_letters:
			last_letters[pairs[i][1]] += 1
		else:
			last_letters[pairs[i][1]] = 1
		if pairs[i] in full_letters:
			full_letters[pairs[i]] += 1
		else:
			full_letters[pairs[i]] = 1
	print(number_of_diff1_pairs)


t = int(input())
for tt in range(t):
	n = int(input())
	d = dict()
	e = dict()
	f = dict()
	s = 0
	for _ in range(n):
		i = input()
		flag = False
		if i in d:
			d[i] = d[i] + 1
			flag = True
		else:
			d[i] = 1
		a = i[0]
		b = i[1]
		if a in e:
			s += e[a]
			s -= d[i] - 1
			e[a] = e[a] + 1
		else:
			e[a] = 1
		if b in f:
			s += f[b]
			s -= d[i] - 1
			f[b] = f[b] + 1
		else:
			f[b] = 1
	print(s)


from collections import defaultdict
test_cases = int(input())

def validstr(inp):
	a = set()
	for i in range(97, 108):
		temp = inp[0] + chr(i)
		temp2 = chr(i) + inp[1]
		if temp != inp:
			a.add(temp)
		if temp2 != inp:
			a.add(temp2)
	return a
for _ in range(test_cases):
	strings = int(input())
	freq = defaultdict(int)
	total = 0
	for i in range(strings):
		freq[input()] += 1
	visited = set()
	for a in list(freq):
		coms = validstr(a)
		for i in coms:
			if i not in visited:
				total += freq[a] * freq[i]
		visited.add(a)
	print(total)


A = []
for _ in range(int(input())):
	A.clear()
	N = int(input())
	for i in range(N):
		A.append(input())
	(c, s) = ({}, {})
	for i in A:
		s[i] = s.get(i, 0) + 1
		c['$' + i[1]] = c.get('$' + i[1], 0) + 1
		c[i[0] + '$'] = c.get(i[0] + '$', 0) + 1
	ans = 0
	for i in c.values():
		ans += i * (i - 1) // 2
	x = 0
	for i in s.values():
		x += i * (i - 1) // 2
	print(ans - x * 2)


def fun(d):
	c = 0
	for x in d:
		c += d[x] * (d[x] - 1) // 2
	return c

def fun2(a, m):
	(d1, d2) = ({}, {})
	for s in a:
		d2[s] = d2.get(s, 0) + 1
		for i in range(m):
			t = s[:i] + '#' + s[i + 1:]
			d1[t] = d1.get(t, 0) + 1
	return fun(d1) - fun(d2) * m
m = 2
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for h in range(n):
		s = input().rstrip()
		a.append(s)
	print(fun2(a, m))


for t in range(int(input())):
	n = int(input())
	dit1 = {}
	dit2 = {}
	dit = {}
	ans = 0
	for i in range(n):
		s = input()
		if s[0] in dit1:
			ans += dit1[s[0]]
			dit1[s[0]] += 1
		else:
			dit1[s[0]] = 1
		if s[1] in dit2:
			ans += dit2[s[1]]
			dit2[s[1]] += 1
		else:
			dit2[s[1]] = 1
		if s in dit:
			ans -= 2 * dit[s]
			dit[s] += 1
		else:
			dit[s] = 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = [input() for _ in range(n)]
	first = {}
	last = {}
	s_dict = {}
	ans = 0
	for i in range(n):
		first[s[i][0]] = first.get(s[i][0], 0) + 1
		last[s[i][1]] = last.get(s[i][1], 0) + 1
		s_dict[s[i]] = s_dict.get(s[i], 0) + 1
		ans = ans + (first[s[i][0]] + last[s[i][1]] - 2 * s_dict[s[i]])
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	m0 = [0] * (ord('k') - ord('a') + 1)
	m1 = [0] * (ord('k') - ord('a') + 1)
	m = defaultdict(int)
	c = 0
	for i in range(n):
		s = input()
		ch0 = ord(s[0]) - ord('a')
		ch1 = ord(s[1]) - ord('a')
		c += m0[ch0]
		c += m1[ch1]
		c -= 2 * m[s]
		m0[ch0] += 1
		m1[ch1] += 1
		m[s] += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	(a1, a2, a3) = ({}, {}, {})
	for i in range(n):
		s = input()
		ans += a1.get(s[0], 0) + a2.get(s[1], 0) - 2 * a3.get(s, 0)
		if s[0] in a1:
			a1[s[0]] += 1
		else:
			a1[s[0]] = 1
		if s[1] in a2:
			a2[s[1]] += 1
		else:
			a2[s[1]] = 1
		if s in a3:
			a3[s] += 1
		else:
			a3[s] = 1
	print(ans)


from collections import Counter
x = int(input())

def cal(n, dic):
	ans = 0
	p = list(dic.keys())
	if len(p) == 1:
		return 0
	for i in range(len(p) - 1):
		(a, b) = (p[i][0], p[i][1])
		for j in range(i + 1, len(p)):
			(c, d) = (p[j][0], p[j][1])
			if a == c and b != d or (a != c and b == d):
				ans += dic[p[i]] * dic[p[j]]
	return ans
for jj in range(x):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(input())
	dic = Counter(arr)
	print(cal(n, dic))


test_numbers = int(input())
results = []
for i in range(test_numbers):
	string_number = int(input())
	branches = {}
	strings_repitition = {}
	strings = []
	result = 0
	for j in range(string_number):
		strings.append(input())
	for j in range(string_number):
		if strings[j][0] + '0' not in branches:
			branches[strings[j][0] + '0'] = []
			branches[strings[j][0] + '0'].append(strings[j])
		else:
			branches[strings[j][0] + '0'].append(strings[j])
		if strings[j][1] + '1' not in branches:
			branches[strings[j][1] + '1'] = []
			branches[strings[j][1] + '1'].append(strings[j])
		else:
			branches[strings[j][1] + '1'].append(strings[j])
		if strings[j] not in strings_repitition:
			strings_repitition[strings[j]] = 1
		else:
			strings_repitition[strings[j]] += 1
	for branch in branches:
		result += len(branches[branch]) * (len(branches[branch]) - 1) / 2
		new_branch = set(branches[branch])
		for string in new_branch:
			result -= strings_repitition[string] * (strings_repitition[string] - 1) / 2
	results.append(int(result))
for result in results:
	print(result)


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		(s, e, w) = (dd(int), dd(int), dd(int))
		f = []
		ans = 0
		for _ in range(n):
			x = rs()
			s[x[0]] += 1
			e[x[1]] += 1
			w[x] += 1
			f.append(x)
		ans = 0
		for i in f:
			ans += s[i[0]] + e[i[1]] - 2 * w[i]
			s[i[0]] -= 1
			e[i[1]] -= 1
			w[i] -= 1
		print(ans)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	words = {}
	for _ in range(n):
		word = input()
		words[word] = words.get(word, 0) + 1
	answer = 0
	for word in words:
		base = word[0]
		for i in range(11):
			anotherWord = base + chr(ord('a') + i)
			if anotherWord == word:
				continue
			if anotherWord in words:
				answer += words[word] * words[anotherWord]
		base = word[1]
		for i in range(11):
			anotherWord = chr(ord('a') + i) + base
			if anotherWord == word:
				continue
			if anotherWord in words:
				answer += words[word] * words[anotherWord]
	print(answer // 2)


test = int(input())
for t in range(test):
	n = int(input())
	d_f = {}
	d_s = {}
	res = 0
	set_str = {}
	for i in range(n):
		s = input()
		if s in set_str.keys():
			set_str[s] += 1
		else:
			set_str[s] = 1
		if s[0] in d_f.keys():
			res += d_f[s[0]] - set_str[s] + 1
			d_f[s[0]] += 1
		else:
			d_f[s[0]] = 1
		if s[1] in d_s.keys():
			res += d_s[s[1]] - set_str[s] + 1
			d_s[s[1]] += 1
		else:
			d_s[s[1]] = 1
	print(res)


t = int(input())
while t:
	t -= 1
	n = int(input())
	(prev, r1, r2) = ({}, {}, {})
	res = 0
	for _ in range(n):
		s = input()
		res += r1.get(s[0], 0) - prev.get(s, 0)
		r1[s[0]] = r1.get(s[0], 0) + 1
		res += r2.get(s[1], 0) - prev.get(s, 0)
		r2[s[1]] = r2.get(s[1], 0) + 1
		prev[s] = prev.get(s, 0) + 1
	print(res)


n = int(input())
for i in range(n):
	count = 0
	m = int(input())
	lst1 = {}
	lst2 = {}
	lst = {}
	for j in range(m):
		strng = input()
		if strng in lst.keys():
			count -= lst[strng] * 2
			lst[strng] += 1
		else:
			lst[strng] = 1
		if strng[0] in lst1.keys():
			lst1[strng[0]] += 1
			count += lst1[strng[0]] - 1
		else:
			lst1[strng[0]] = 1
		if strng[1] in lst2.keys():
			lst2[strng[1]] += 1
			count += lst2[strng[1]] - 1
		else:
			lst2[strng[1]] = 1
	print(count)


n = int(input())
for _ in range(n):
	t = int(input())
	sl = {}
	sl_b1 = {}
	sl_b2 = {}
	res = 0
	for i in range(t):
		b = input()
		if b[0] in sl_b1:
			res += sl_b1[b[0]]
		if b in sl:
			res -= sl[b]
		if b[1] in sl_b2:
			res += sl_b2[b[1]]
		if b in sl:
			res -= sl[b]
		if b in sl:
			sl[b] += 1
		else:
			sl[b] = 1
		if b[0] in sl_b1:
			sl_b1[b[0]] += 1
		else:
			sl_b1[b[0]] = 1
		if b[1] in sl_b2:
			sl_b2[b[1]] += 1
		else:
			sl_b2[b[1]] = 1
	print(res)


from collections import defaultdict
from email.policy import default
tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = [input() for _ in range(n)]
	(s, e) = (defaultdict(lambda : 0), defaultdict(lambda : 0))
	check = defaultdict(lambda : 0)
	ans = 0
	for x in arr:
		check[x] += 1
		(a, b) = (x[0], x[1])
		ans += s[a] + e[b]
		s[a] += 1
		e[b] += 1
	for i in check:
		if check[i] > 1:
			ans -= check[i] * (check[i] - 1)
	print(ans)


def solve():
	for N in range(int(input())):
		n = int(input())
		dic = {}
		for j in range(n):
			c = input()
			if c in dic:
				dic[c] += 1
			else:
				dic[c] = 1
		dic2 = {}
		total = 0
		ar = list(dic.keys())
		for j in range(len(ar)):
			for i in range(j + 1, len(ar)):
				(word1, word2) = (ar[i], ar[j])
				if word1[0] == word2[0] or word1[1] == word2[1]:
					total += dic[word1] * dic[word2]
		print(total)
solve()


for _ in range(int(input())):
	n = int(input())
	l1 = [0] * 11
	l2 = [0] * 11
	l12 = []
	for i in range(11):
		l12.append([0] * 11)
	ans = 0
	for i in range(n):
		s = input()
		ans += l1[ord(s[0]) - 97]
		ans += l2[ord(s[1]) - 97]
		ans -= 2 * l12[ord(s[0]) - 97][ord(s[1]) - 97]
		l1[ord(s[0]) - 97] += 1
		l2[ord(s[1]) - 97] += 1
		l12[ord(s[0]) - 97][ord(s[1]) - 97] += 1
	print(ans)