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

Chef is learning English. So far, he knows $N$ words, and he wants to write a verse.

Let's call a pair of English words a *stanza*. A *verse* is a list of stanzas. The *prefixal rhyme* of a stanza is the longest common prefix of the words in it. Similarly, the *suffixal rhyme* of a stanza is the longest common suffix of the words in it. The *beauty* of a stanza whose prefixal and suffixal rhymes have lengths $l_{p}$ and $l_{s}$ respectively is $\mathrm{min}(l_{p}, l_{s})^2$.

For example, a stanza formed by the words "abcdefghijkl" and "abcxyzhijkl" has a prefixal rhyme "abc" (with length $3$), suffixal rhyme "hijkl" (with length $5$) and beauty $\mathrm{min}(3,5)^2 = 3^{2} = 9$.

The beauty of a verse is the sum of beauties of all its stanzas. For example, the beauty of the verse (("abcdefghijkl", "abcxyzhijkl"), ("world", "word"), ("code", "chef")) is $9+1+0=10$.

You are given $N$ words $W_{1}, W_{2}, \ldots, W_{N}$ (they are not necessarily distinct). Help Chef write the most beautiful verse. It is not necessary to use all the words, but each word may be used at most once in the whole verse (more precisely, each element of the sequence $W$ may be used only once, but if some word appears $k$ times in $W$, we can use it up to $k$ times).

------  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 $W_{i}$.

------  Output ------
For each test case, print a single line containing one integer ― the greatest possible beauty of Chef's verse.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ |W_{i}| ≤ 10^{5}$ for each valid $i$
all words contain only lowercase English letters
the sum of $|W_{1}|+|W_{2}|+\ldots+|W_{N}|$ over all test cases does not exceed $10^{5}$

------  Subtasks ------
Subtask #1 (50 points): all words are palindromes

Subtask #2 (50 points): original constraints

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

6

abcdefghijkl

chef

world

code

abcxyzhijkl

word

4

problem

poem

problem

problem

3

contest

coolest

unused
----- Sample Output 1 ------ 
10

50

4
----- explanation 1 ------ 
Example case 1: The best verse is (("abcdefghijkl", "abcxyzhijkl"), ("world", "word"), ("code", "chef")), which was described above.

Example case 2: The best verse is (("problem", "problem"), ("problem", "poem")). Its beauty is $7^{2}+1^{2} = 49+1 = 50$. Note that we have three copies of the word "problem", so we can use it three times.

Example case 3: The best verse is (("coolest", "contest")), which contains only one stanza. Its beauty is $2^{2}=4$. Note that it is not necessary to use all the words ? the word "unused" is left unused.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

String algorithms

Greedy algorithms

Data structures


Solutions:
def change(u):
	i = 0
	N = len(u)
	v = u[::-1]
	new = ''
	for i in range(N):
		new += u[i] + v[i]
	return new
T = int(input())
for nnn in range(T):
	k = []
	N = int(input())
	for i in range(N):
		u = input()
		u = change(u)
		k.append(u)
	k.sort()
	tt = []
	ttt = 0
	i = 0
	newarr = []
	if len(tt) < 0:
		a = 'abcdefghijklmnopqrstuvwxyz'
		b = 0
		for i in a:
			m = []
			for j in range(b, len(k)):
				if i == k[j][0]:
					m.append(k[j])
				else:
					b = j
					break
			newarr.append(m)
		ttt = 0
		for d in newarr:
			if len(d) <= 1:
				continue
			while len(d) >= 1:
				i = 0
				arr_indexes = 0
				max1 = 0
				while i < len(d) - 1:
					u = 0
					for j in range(min(len(d[i]), len(d[i + 1]))):
						if d[i][j] == d[i + 1][j]:
							u += 1
						else:
							break
					if u > 0:
						if max1 < u:
							max1 = u
							arr_indexes = i
						i += 1
					else:
						i += 1
				try:
					d.pop(arr_indexes)
					d.pop(arr_indexes)
				except:
					break
				ttt += max1 * max1

	def my(k, mmm):
		mini = 1000000000000
		index = 0
		for i in range(0, len(k) - 1):
			u = 0
			for j in range(min(len(k[i]), len(k[i + 1]))):
				if k[i][j] == k[i + 1][j]:
					u += 1
				else:
					break
			if mini > u:
				mini = u
				index = i
		if k[0] == k[-1]:
			c = len(k) // 2 * len(k[0]) * len(k[0]) // 4
			if len(k) % 2 == 0:
				return (0, 0, c)
			else:
				return (1, mmm.index(k[0]), c)
		if len(k) == 1:
			return (1, mmm.index(k[0]), 0)
		if len(k) == 2:
			mini = mini // 2
			return (0, 0, mini * mini)
		a1 = my(k[:index + 1], mmm)
		a2 = my(k[index + 1:], mmm)
		if a1[0] == 1 and a2[0] == 1:
			u = 0
			for j in range(min(len(mmm[a1[1]]), len(mmm[a2[1]]))):
				if mmm[a1[1]][j] == mmm[a2[1]][j]:
					u += 1
				else:
					break
			u = u // 2
			return (0, 0, a1[2] + a2[2] + u * u)
		elif a1[0] == 1 and a2[0] == 0:
			return (1, a1[1], a1[2] + a2[2])
		elif a1[0] == 0 and a2[0] == 1:
			return (1, a2[1], a1[2] + a2[2])
		else:
			return (0, 0, a1[2] + a2[2])
	mmm = k[:]
	a = my(k, mmm)
	print(a[2])


def calbeauty(word1, word2):
	p = 0
	i = 0
	a = len(word1)
	b = len(word2)
	k = min(a, b)
	while i < k:
		if word1[i] == word2[i]:
			i = i + 1
			p = p + 1
		else:
			break
	return i // 2
for _ in range(int(input())):
	N = int(input())
	Word = []
	from collections import defaultdict
	d = defaultdict(int)
	for j in range(N):
		w = input()
		d[w] += 1
	beauty = 0
	for item in d:
		f = d[item]
		if f % 2 == 1:
			Word.append(item)
			data = len(item) ** 2
			q = f // 2
			beauty = beauty + q * data
		else:
			data = len(item) ** 2
			q = f // 2
			beauty = beauty + q * data
	W = []
	for w in Word:
		i = 0
		itsL = []
		for i in range(len(w)):
			itsL.append(w[i])
			itsL.append(w[-i - 1])
		W.append(tuple(itsL))
	Lists = defaultdict(list)
	for item in W:
		Lists[item[0] + item[1]].append(item)
	for c in Lists:
		W = sorted(Lists[c])
		count = len(W)
		while count > 0:
			count = count - 1
			Remain = []
			while len(W) > 2:
				data1 = calbeauty(W[-1], W[-2])
				data2 = calbeauty(W[-2], W[-3])
				if data2 <= data1:
					beauty = beauty + data1 ** 2
					W.pop()
					W.pop()
				else:
					d = W.pop()
					Remain.append(d)
			if len(Remain) == 0:
				break
			else:
				W.extend(Remain)
				W.sort()
		while len(W) > 2:
			if len(W) >= 4:
				data1 = calbeauty(W[-1], W[-2])
				data2 = calbeauty(W[-2], W[-3])
				data3 = calbeauty(W[-3], W[-4])
				beauty = beauty + max(data1, data2, data3) ** 2
				if data1 >= data2 and data1 >= data3:
					W.pop()
					W.pop()
				elif data2 >= data1 and data2 >= data3:
					W.pop(-2)
					W.pop(-2)
				elif data3 >= data2 and data3 >= data1:
					W.pop(-3)
					W.pop(-3)
			else:
				data1 = calbeauty(W[0], W[1])
				data2 = calbeauty(W[1], W[2])
				if data2 <= data1:
					beauty = beauty + data1 ** 2
					W.pop()
					W.pop()
				else:
					beauty = beauty + data2 ** 2
					W.pop(-2)
					W.pop(-2)
		if len(W) == 1 or len(W) == 0:
			continue
		else:
			beauty = beauty + calbeauty(W[0], W[1]) ** 2
	print(beauty)


import string
import math
import time
import sys
from typing import List, Dict, Tuple

class Solution:

	def __init__(self):
		self.TIMEDIFF = 6.0
		self.DELTA = 0.5

	def __len__(self):
		return 0

	def maxVersePalindrome(self, A: List[str], op: bool, d: dict) -> int:
		if not op:
			m = dict()
			for a in A:
				s = ''
				for char in a:
					s += char
					if s in m:
						m[s] += 1
					else:
						m[s] = 1
		else:
			m = d
		count = 0
		for a in A:
			local_count = 0
			s = ''
			if m.get(a) == 0:
				continue
			for i in range(len(a)):
				s += a[i]
				curr_count = m.get(s)
				if curr_count == 1:
					last_char = s[-1]
					s = s[:-1]
					break
				else:
					local_count += 1
			if len(s) == 0:
				continue
			elif local_count == len(a):
				last_char = 'Z'
			if abs(m.get(s) - self.nChildrenPalindrome(s, m)) >= 2:
				count += math.pow(local_count, 2)
				b = ''
				for char in a:
					b += char
					m[b] -= 2
			else:
				letters = string.ascii_lowercase
				matched = False
				while s != '' and (not matched):
					for l in letters:
						f = s + l
						if l != last_char and f in m and (m.get(f) > 0) and (m.get(f) % 2 != 0):
							s += l
							matched = not False
							break
					if not matched:
						local_count -= 1
						last_char = s[-1]
						s = s[:-1]
					else:
						while self.nChildrenPalindrome(s, m) % 2 == 1:
							for l in letters:
								f = s + l
								if f in m and m.get(f) > 0 and (m.get(f) % 2 != 0):
									s += l
									break
				if len(s) != 0 or s != '':
					b = ''
					count += math.pow(local_count, 2)
					for char in a:
						b += char
						m[b] -= 1
					b = ''
					for char in s:
						b += char
						m[b] -= 1
		return int(count)

	def maxVerseNormal(self, A: list, time_init: float) -> int:
		letters = string.ascii_lowercase
		count = 0
		(fs, m, u) = (dict(), dict(), dict())
		for a in A:
			(f, b) = ('', '')
			for i in range(len(a)):
				f += a[i]
				b += a[len(a) - i - 1]
				if f in fs:
					fs[f] += 1
				else:
					fs[f] = 1
				result = self.concatStr(f, '|', b)
				if result in m:
					m[result] += 1
				else:
					m[result] = 1
			if a in u:
				u[a] += 1
			else:
				u[a] = 1
		t_final = time.time()
		diff = abs(t_final - time_init)
		if diff >= self.TIMEDIFF:
			if abs(diff - self.TIMEDIFF) <= self.DELTA:
				return self.maxVersePalindrome(A, True, fs)
		for a in A:
			if u[a] == 0:
				continue
			(f, b) = ('', '')
			local_count = 0
			for i in range(len(a)):
				f += a[i]
				b += a[len(a) - i - 1]
				concat = self.concatStr(f, '|', b)
				currCount = m.get(concat)
				if currCount == 1:
					lastChar = f[-1] + '|' + b[-1]
					f = f[:-1]
					b = b[:-1]
					break
				else:
					local_count += 1
			if f == '' or b == '':
				continue
			elif local_count == len(a):
				lastChar = 'Z'
			if abs(m.get(self.concatStr(f, '|', b)) - self.nChildrenNormal(f, b, m, fs, letters)) >= 2:
				(p, q) = ('', '')
				for i in range(len(a)):
					p += a[i]
					q += a[len(a) - i - 1]
					m[self.concatStr(p, '|', q)] -= 2
				u[a] -= 2
				count += math.pow(local_count, 2)
			else:
				matched = not True
				while not matched and (f != '' and b != ''):
					for l1 in letters:
						fw = f + l1
						if fw not in fs:
							continue
						for l2 in letters:
							s = self.concatStr(fw, '|', b, l2)
							if self.concatStr(l1, '|', l2) != lastChar and s in m and (m.get(s) % 2 != 0) and (m.get(s) > 0):
								(f, b) = (f + l1, b + l2)
								matched = True
								break
						if matched:
							break
					if not matched:
						lastChar = self.concatStr(f[-1], '|', b[-1])
						(f, b) = (f[:-1], b[:-1])
						local_count -= 1
					else:
						while self.nChildrenNormal(f, b, m, fs, letters) % 2 == 1:
							for l1 in letters:
								flag = False
								fw = f + l1
								if fw not in fs:
									continue
								for l2 in letters:
									bw = b + l2
									s = self.concatStr(fw, '|', bw)
									if s in m and m.get(s) % 2 != 0 and (m.get(s) > 0):
										flag = True
										(f, b) = (f + l1, b + l2)
										break
								if flag:
									break
				if f != '' and b != '':
					u[a] -= 1
					u[f] -= 1
					count += math.pow(local_count, 2)
					(p, q) = ('', '')
					for i in range(len(a)):
						p += a[i]
						q += a[len(a) - i - 1]
						m[self.concatStr(p, '|', q)] -= 1
					(p, q) = ('', '')
					for i in range(len(f)):
						p += f[i]
						q += b[i]
						m[self.concatStr(p, '|', q)] -= 1
		return int(count)

	def nChildrenNormal(self, f: str, b: str, m: dict, fs: list, letters: str) -> int:
		count = 0
		for l1 in letters:
			forward = f + l1
			if forward not in fs:
				continue
			for l2 in letters:
				lookfor = self.concatStr(forward, '|', b, l2)
				if lookfor in m:
					count += m.get(lookfor)
		return count

	def isPal(self, s: str) -> bool:
		return s == s[::-1]

	def concatStr(self, *args) -> str:
		s = ''
		for arg in args:
			s += arg
		return s

	def nChildrenPalindrome(self, s: str, m: dict) -> int:
		letters = string.ascii_lowercase
		count = 0
		for l in letters:
			search = s + l
			if search in m:
				count += m[search]
		return count

	def solve(self) -> None:
		t = int(sys.stdin.readline())
		t_init = time.time()
		buffer_out = ''
		for test_case in range(t):
			pal = False
			n_strings = int(sys.stdin.readline())
			A = []
			for _ in range(n_strings):
				x = sys.stdin.readline().split()[0]
				if not pal and (not self.isPal(x)):
					pal = True
				A.append(x)
			A = sorted(A)
			if pal:
				buffer_out += str(self.maxVerseNormal(A, t_init))
				buffer_out += '\n'
			else:
				buffer_out += str(self.maxVersePalindrome(A, False, {}))
				buffer_out += '\n'
		sys.stdout.write(buffer_out)
s = Solution()
s.solve()


def rhyme(word1, word2):
	c = 0
	while c < len(word1) and c < len(word2) and (word1[c] == word2[c]) and (word1[-1 - c] == word2[-1 - c]):
		c += 1
	return c ** 2

def solve(words):
	(count, beauty, beauties) = ({}, 0, [])
	for word in words:
		if word not in count:
			count[word] = 0
		count[word] += 1
	for word in count:
		if count[word] >= 2:
			beauty += rhyme(word, word) * (count[word] // 2)
			count[word] = count[word] % 2
	for word1 in count:
		for word2 in count:
			if word1 != word2:
				if rhyme(word1, word2) > 0:
					beauties.append((rhyme(word1, word2), word1, word2))
	beauties.sort(key=lambda x: x[0], reverse=True)
	for (b, word1, word2) in beauties:
		if count[word1] > 0 and count[word2] > 0:
			(count[word1], count[word2], beauty) = (count[word1] - 1, count[word2] - 1, beauty + b)
	return beauty
for _ in range(int(input())):
	(n, words) = (int(input()), [])
	for i in range(n):
		words.append(input())
	print(solve(words))


class Node:

	def __init__(self, value, L):
		self.value = value
		self.count = 1
		self.L = L
		self.R = dict()

	def increment(self):
		self.count += 1

	@staticmethod
	def encode(c_1, c_0):
		return (c_1 - 97) * 26 + (c_0 - 97)

	def add_node(self, value):
		if value in self.R:
			self.R[value].increment()
		else:
			self.R[value] = Node(value, self)
		return self.R[value]

	def get_pair_length(self):
		length = 0
		node = self
		while node != None and node.count > 1:
			length += 1
			node.count -= 2
			node = node.find_most_frequent()
		return length

	def find_most_frequent(self):
		max_count = 1
		max_count_node = None
		for node in self.R.values():
			if node.count > max_count:
				max_count = node.count
				max_count_node = node
		return max_count_node

	def solve(self):
		total_beauty = 0
		stanza_beauty = 0
		node = self.find_most_frequent()
		while node != None:
			stanza_beauty = int(node.get_pair_length())
			stanza_beauty *= stanza_beauty
			total_beauty += stanza_beauty
			node = self.find_most_frequent()
		return total_beauty

	def load(self, line):
		node = self
		for i in range(0, len(line)):
			j = len(line) - 1 - i
			value = line[i] + line[j]
			node = node.add_node(value)

	def print(self, depth):
		str = ''
		for i in range(0, depth):
			str += '-'
		print(f'{str} {self.value} {self.count}')
		depth += 1
		for node in self.R.values():
			node.print(depth)

def main():
	T = int(input())
	for t in range(0, T):
		root = Node(1000, 'None')
		N = int(input())
		for n in range(0, N):
			line = input()
			root.load(line)
		beauty = root.solve()
		print(beauty)
main()


global ans
ans = 0

def lmatch(a, b):
	match = 0
	for i in range(min(len(a), len(b))):
		if a[i] == b[i]:
			match += 1
		else:
			break
	return int(match / 2) ** 2
tc = int(input())
for tc_i in range(tc):
	arr = []
	n = int(input())
	for n_i in range(n):
		x = input()
		nx = ''
		for i in range(len(x)):
			nx = nx + x[i] + x[len(x) - i - 1]
		arr.append(nx)
	arr.sort()

	def recursive(st, fin):
		ans = 0
		if st == fin:
			return [1, st, ans]
		elif st + 1 == fin:
			x = lmatch(arr[st], arr[fin])
			ans = ans + x
			return [0, 0, ans]
		elif arr[st] == arr[fin]:
			total = fin - st + 1
			x = total // 2 * lmatch(arr[st], arr[fin])
			if 1 & total:
				return [1, st, x]
			return [0, 0, x]
		index = st
		minsc = 100000000
		for i in range(st, fin):
			tsc = lmatch(arr[i], arr[i + 1])
			if tsc < minsc:
				index = i
				minsc = tsc
		f1 = recursive(st, index)
		f2 = recursive(index + 1, fin)
		if f1[0] == 1 and f2[0] == 1:
			x = lmatch(arr[f1[1]], arr[f2[1]])
			return [0, 0, f1[2] + f2[2] + x]
		elif f1[0] == 1 and f2[0] == 0:
			return [1, f1[1], f1[2] + f2[2]]
		elif f1[0] == 0 and f2[0] == 1:
			return [1, f2[1], f1[2] + f2[2]]
		else:
			return [0, 0, f1[2] + f2[2]]
	q = recursive(0, n - 1)[-1]
	print(q)


import heapq

def beauty(word1, word2):
	try:
		for (i, w) in enumerate(word1):
			if w != word2[i] or word1[-1 - i] != word2[-1 - i]:
				return i
		else:
			return i + 1
	except:
		return i

def findBeauty():
	for i in range(N - 1):
		for j in range(i + 1, N):
			b = beauty(unique_words[i], unique_words[j])
			if b:
				heapq.heappush(beauties, (-b, (i, j)))

def removeDuplicate():
	dic = {}
	unique_words = []
	for word in Words:
		if word not in dic.keys():
			dic[word] = 1
		else:
			dic[word] += 1
	total_beauty = 0
	for (word, count) in dic.items():
		if count == 1:
			unique_words.append(word)
		else:
			total_beauty += count // 2 * len(word) ** 2
			if count % 2:
				unique_words.append(word)
	return (total_beauty, unique_words)

def solve(total_beauty):
	used = set()
	while len(beauties) > 0:
		(b, (i, j)) = heapq.heappop(beauties)
		if i in used or j in used:
			continue
		total_beauty += b ** 2
		used.add(i)
		used.add(j)
	return total_beauty
T = int(input())
for _ in range(T):
	Words = []
	N = int(input())
	for n in range(N):
		Words.append(input())
	(total_beauty, unique_words) = removeDuplicate()
	N = len(unique_words)
	beauties = []
	heapq.heapify(beauties)
	findBeauty()
	print(solve(total_beauty))


t = int(input())

class TrieNode:

	def __init__(self):
		self.children = [None] * 26 * 26
		self.count = 0
		self.length = 0

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def char_to_index(self, char1, char2):
		index1 = ord(char1) - ord('a')
		return index1 * 26 + (ord(char2) - ord('a'))

	def insert(self, key):
		pcrawl = self.root
		length = len(key)
		for level in range(length):
			index = self.char_to_index(key[level], key[length - 1 - level])
			if not pcrawl.children[index]:
				pcrawl.children[index] = self.getNode()
			pcrawl = pcrawl.children[index]
			pcrawl.count += 1
			pcrawl.length = level + 1

	def DFS(self):
		stack = []
		beauty = 0
		pcrawl = self.root
		for i in range(26 * 26):
			if pcrawl.children[i] != None and pcrawl.children[i].count > 1:
				stack.append((pcrawl.children[i], pcrawl.children[i].length))
		while len(stack) != 0:
			node = stack.pop()
			beauty += int(node[0].count / 2) * (pow(node[1], 2) - pow(node[1] - 1, 2))
			for i in range(26 * 26):
				if node[0].children[i] != None and node[0].children[i].count > 1:
					stack.append((node[0].children[i], node[0].children[i].length))
		print(beauty)
for i in range(t):
	n = int(input())
	word_list = []
	for j in range(n):
		word_list.append(input())
	T = Trie()
	for key in word_list:
		T.insert(key)
	T.DFS()


from collections import defaultdict

def check(aa, bb):
	l = 0
	r = -1
	counter = 0
	for _ in range(min(len(aa), len(bb))):
		if aa[l] == bb[l] and aa[r] == bb[r]:
			counter += 1
		else:
			return counter
		l += 1
		r -= 1
	return counter
for _ in range(int(input())):
	N = int(input())
	word = []
	dic = defaultdict(int)
	for __ in range(N):
		x = input()
		dic[x] += 1
	ans = 0
	for (w, n) in dic.items():
		if n % 2 == 0:
			ans += len(w) ** 2 * (n // 2)
		else:
			ans += len(w) ** 2 * (n // 2)
			word.append(w)
	wordTup = []
	for i in range(len(word)):
		for j in range(len(word)):
			if i != j:
				key = check(word[i], word[j])
				if key > 0:
					wordTup.append((key, word[i], word[j]))
	ss = set()
	wordTup.sort(key=lambda x: x[0], reverse=True)
	for i in wordTup:
		if i[1] not in ss and i[2] not in ss:
			ans += i[0] ** 2
			ss.add(i[1])
			ss.add(i[2])
	print(ans)


def check(s1, s2):
	m = min(len(s1), len(s2))
	r = -1
	i = 0
	count = 0
	while i < m and r >= -m and (s1[i] == s2[i]) and (s1[r] == s2[r]):
		count += 1
		i += 1
		r -= 1
	return count
for _ in range(int(input())):
	n = int(input())
	words = []
	for i in range(n):
		words.append(input())
	d = {}
	for i in words:
		if d.get(i) == None:
			d[i] = 1
		else:
			d[i] += 1
	ans = 0
	words = []
	for (i, j) in d.items():
		if j % 2 == 0:
			ans += len(i) ** 2 * (j // 2)
		else:
			ans += len(i) ** 2 * (j // 2)
			words.append(i)
	arr = []
	for i in range(len(words)):
		for j in range(len(words)):
			if i != j:
				ret = check(words[i], words[j])
				if ret > 0:
					arr.append((ret, words[i], words[j]))
	arr.sort(key=lambda x: x[0], reverse=True)
	s = set()
	for item in arr:
		if item[1] not in s and item[2] not in s:
			ans += item[0] ** 2
			s.add(item[1])
			s.add(item[2])
	print(ans)


def common(a, b):
	m = min(len(a), len(b))
	i = 0
	r = -1
	count = 0
	while i < m and r >= -m and (a[i] == b[i]) and (a[r] == b[r]):
		count += 1
		i += 1
		r -= 1
	return count

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		arr = []
		for i in range(n):
			arr.append(input())
		d = {}
		ans = 0
		for i in arr:
			if d.get(i) == None:
				d[i] = 1
			else:
				d[i] += 1
		words = []
		for (i, j) in d.items():
			if j % 2 == 0:
				ans += len(i) ** 2 * (j // 2)
			else:
				ans += len(i) ** 2 * (j // 2)
				words.append(i)
		s = set()
		arr1 = []
		for i in range(len(words)):
			for j in range(i + 1, len(words)):
				if i != j:
					r = common(words[i], words[j])
					if r > 0:
						arr1.append((r, words[i], words[j]))
		arr1.sort(key=lambda x: x[0], reverse=True)
		s = set()
		for i in arr1:
			if i[1] not in s and i[2] not in s:
				ans += i[0] ** 2
				s.add(i[1])
				s.add(i[2])
		print(ans)
		t -= 1
main()


def rhyme(word1, word2):
	c = 0
	while c < len(word1) and c < len(word2) and (word1[c] == word2[c]) and (word1[-1 - c] == word2[-1 - c]):
		c += 1
	return c ** 2

def solve(words, n):
	count = {}
	for word in words:
		if word not in count:
			count[word] = 0
		count[word] += 1
	beauty = 0
	for word in count:
		if count[word] >= 2:
			beauty += rhyme(word, word) * (count[word] // 2)
			count[word] = count[word] % 2
	beauties = []
	for word1 in count:
		for word2 in count:
			if word1 != word2:
				if count[word1] > 0 and count[word2] > 0:
					b = rhyme(word1, word2)
					if b > 0:
						beauties.append((b, word1, word2))
	beauties = sorted(beauties, key=lambda x: x[0], reverse=True)
	for (b, word1, word2) in beauties:
		if count[word1] > 0 and count[word2] > 0:
			count[word1] -= 1
			count[word2] -= 1
			beauty += b
	return beauty
T = int(input().strip())
for problem in range(1, T + 1):
	n = int(input().strip())
	words = []
	for word in range(n):
		words.append(input().strip())
	print(solve(words, n))


def check(x, y):
	ans = 0
	left = 0
	right = -1
	z = min(len(x), len(y))
	while left < z and right >= -z and (x[left] == y[left]) and (x[right] == y[right]):
		ans += 1
		left += 1
		right -= 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for x in range(n):
		l.append(input())
	d = {}
	for x in list(l):
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	ans = 0
	l = []
	for x in dict(d):
		if d[x] % 2 == 0:
			ans += len(x) ** 2 * (d[x] // 2)
		else:
			ans += len(x) ** 2 * (d[x] // 2)
			l.append(x)
	arr = []
	for x in list(l):
		for y in list(l):
			if x == y:
				continue
			else:
				val = check(x, y)
				if val > 0:
					arr.append((val * val, x, y))
	arr.sort(key=lambda x: x[0], reverse=True)
	s = set()
	for x in arr:
		if x[1] not in s and x[2] not in s:
			ans += x[0]
			s.add(x[1])
			s.add(x[2])
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	ref = dict()
	mai = dict()
	for i in range(n):
		a = input().rstrip()
		if a not in mai:
			mai[a] = 1
		else:
			mai[a] += 1
		ref[a] = 0
	b = []
	res = 0
	for i in mai.keys():
		if mai[i] >= 2:
			res += pow(len(i), 2) * (mai[i] // 2)
			if mai[i] % 2:
				b.append(i)
			continue
		b.append(i)
	l1 = len(b)
	fi = []
	for i in range(l1):
		for j in range(l1):
			if i == j:
				continue
			l = 0
			r = min(len(b[i]), len(b[j]))
			r1 = r
			r -= 1
			p = len(b[i]) - 1
			p1 = len(b[j]) - 1
			c = 0
			while l <= r1 - 1 and r >= 0 and (b[i][l] == b[j][l]) and (b[i][p] == b[j][p1]):
				c += 1
				l += 1
				r -= 1
				p -= 1
				p1 -= 1
			if c > 0:
				fi.append([c, b[i], b[j]])
	fi.sort(reverse=True)
	for i in fi:
		if ref[i[1]] == 0 and ref[i[2]] == 0:
			res += pow(i[0], 2)
			ref[i[1]] = 1
			ref[i[2]] = 1
	print(res)


def check(s1, s2):
	i = -1
	for i in range(min(len(s1), len(s2))):
		if s1[i] != s2[i]:
			i = i - 1
			break
	mi = i + 1
	i = len(s1) - 1
	j = len(s2) - 1
	n = 0
	while i >= 0 and j >= 0:
		if s1[i] != s2[j]:
			break
		n += 1
		i = i - 1
		j = j - 1
	if n < mi:
		mi = n
	return mi

def func(l):
	d = {}
	d2 = {}
	for i in l:
		d[i] = 0
	n = len(l)
	for i in range(n):
		if d[l[i]] == 0:
			for j in range(i + 1, n):
				m = check(l[i], l[j])
				if m in d2:
					d2[m].append((l[i], l[j]))
				else:
					d2[m] = [(l[i], l[j])]
		d[l[i]] += 1
	list = []
	val = 0
	for j in d2.keys():
		list.append(j)
	list.sort(reverse=True)
	for i in list:
		for j in d2[i]:
			if d[j[0]] > 0:
				d[j[0]] -= 1
				if d[j[1]] > 0:
					d[j[1]] -= 1
					val += i ** 2
				else:
					d[j[0]] += 1
	return val
t = int(input())
for fber in range(t):
	n = int(input())
	l = []
	for gi5t in range(n):
		l.append(input())
	ns = func(l)
	print(ns)


import sys
sys.setrecursionlimit(10 ** 5 + 1)
rr = lambda : input().strip()
rri = lambda : int(rr())
rrm = lambda : [int(x) for x in rr().split()]

class node(object):

	def __init__(self, d=0):
		self.nodes = [None] * 676
		self.c = 0
		self.d = d

	def ce(self, con):
		if con:
			self.c += 1

	def sc(self, c):
		self.c = c

	def gd(self):
		return self.d

	def gc(self):
		return self.c

class trie(object):

	def __init__(self):
		self.root = node()

	def addn(self, s):
		nd = self.root
		for i in s:
			if nd.nodes[i] == None:
				nd.nodes[i] = node(nd.gd() + 1)
			nd = nd.nodes[i]
		nd.ce(True)

def getint(ch1, ch2):
	return (ord(ch1) - ord('a')) * 26 + ord(ch2) - ord('a')
res = 0

def dfs(nd):
	global res
	k = 0
	for i in range(676):
		if nd.nodes[i] != None:
			k += dfs(nd.nodes[i])
	k += nd.gc()
	res += nd.gd() ** 2 * (k // 2)
	return k % 2

def sol():
	n = rri()
	if n == 1:
		rr()
		return 0
	lis = []
	tr = trie()
	for i in range(n):
		s = rr()
		t = s[::-1]
		k = []
		for j in range(len(s)):
			k.append(getint(s[j], t[j]))
		tr.addn(k)
	global res
	res = 0
	dfs(tr.root)
	return res
T = rri()
for _ in range(T):
	ans = sol()
	print(ans)


t = int(input())
while t:
	inp = []
	n = int(input())
	for i in range(n):
		inp.append(input())
	d = {}
	for i in inp:
		if d.get(i) is None:
			d[i] = 1
		else:
			d[i] += 1
	ans = 0
	words = []
	for (i, j) in d.items():
		if j % 2 == 0:
			ans += len(i) ** 2 * (j // 2)
		else:
			ans += len(i) ** 2 * (j // 2)
			words.append(i)
	arr = []
	for i in words:
		for j in words:
			count = 0
			if i != j:
				p1 = 0
				p2 = -1
				m = min(len(i), len(j))
				while p1 < m and p2 >= -m and (i[p1] == j[p1]) and (i[p2] == j[p2]):
					p1 += 1
					p2 -= 1
					count += 1
				if count > 0:
					arr.append((count, i, j))
	arr.sort(key=lambda x: x[0], reverse=True)
	s = set()
	for i in arr:
		if i[1] not in s and i[2] not in s:
			ans += i[0] ** 2
			s.add(i[1])
			s.add(i[2])
	print(ans)
	t = t - 1


def beauty(s1, s2):
	l = min(len(s1), len(s2))
	i = 0
	j = -1
	c = 0
	while i < l and s1[i] == s2[i] and (s1[j] == s2[j]):
		i += 1
		j -= 1
		c += 1
	return c * c
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	ans = 0
	l = []
	for (i, j) in d.items():
		if j % 2 == 1:
			l.append(i)
		ans += d[i] // 2 * len(i) ** 2
	res = []
	for i in range(0, len(l)):
		for j in range(i + 1, len(l)):
			ret = beauty(l[i], l[j])
			if ret > 0:
				res.append((ret, l[i], l[j]))
	res = sorted(res, key=lambda x: x[0], reverse=True)
	s = set()
	for ele in res:
		if ele[1] not in s and ele[2] not in s:
			s.add(ele[1])
			s.add(ele[2])
			ans += ele[0]
	print(ans)


def beauty(w1, w2):
	m = min(len(w1), len(w2))
	l = 0
	r = -1
	num = 0
	while l < m and r >= -m and (w1[l] == w2[l]) and (w1[r] == w2[r]):
		num += 1
		l += 1
		r -= 1
	return num ** 2
T = int(input())
while T:
	N = int(input())
	List = []
	from collections import defaultdict
	D = defaultdict(int)
	for i in range(N):
		word = input()
		List.append(word)
		D[word] += 1
	ans = 0
	List = []
	for (i, j) in D.items():
		ans += len(i) ** 2 * (j // 2)
		if j % 2 != 0:
			List.append(i)
	arr = []
	for i in range(len(List)):
		for j in range(len(List)):
			if i == j:
				continue
			else:
				val = beauty(List[i], List[j])
				arr.append((val, List[i], List[j]))
	arr.sort(key=lambda X: X[0], reverse=True)
	set1 = set()
	for i in arr:
		if i[1] not in set1 and i[2] not in set1:
			ans += i[0]
			set1.add(i[1])
			set1.add(i[2])
	print(ans)
	T -= 1


def findPairsVal(s1, s2):
	n = min(len(s1), len(s2))
	s = 0
	e = -1
	cnt = 0
	while s < n and e >= -n and (s1[s] == s2[s]) and (s1[e] == s2[e]):
		cnt += 1
		s += 1
		e -= 1
	return cnt ** 2
for t in range(int(input())):
	words = []
	for n in range(int(input())):
		words.append(input())
	d = {}
	for w in words:
		if d.get(w) == None:
			d[w] = 1
		else:
			d[w] += 1
	words = []
	ans = 0
	for (i, j) in d.items():
		ans += len(i) ** 2 * (j // 2)
		if j & 1:
			words.append(i)
	arr = []
	for i in range(len(words)):
		for j in range(len(words)):
			if i != j:
				temp = findPairsVal(words[i], words[j])
				if temp > 0:
					arr.append((temp, words[i], words[j]))
	arr.sort(key=lambda x: x[0], reverse=True)
	s = set()
	for ele in arr:
		if ele[1] not in s and ele[2] not in s:
			s.add(ele[1])
			s.add(ele[2])
			ans += ele[0]
	print(ans)


def fun(s1, s2):
	start = 0
	end = -1
	min_length = min(len(s1), len(s2))
	c = 0
	while start < min_length and end >= -min_length and (s1[start] == s2[start]) and (s1[end] == s2[end]):
		c += 1
		start += 1
		end -= 1
	return c
for _ in range(int(input())):
	n = int(input())
	words = []
	for i in range(n):
		words.append(input())
	h = dict()
	for i in words:
		if i not in h:
			h[i] = 1
		else:
			h[i] += 1
	words = []
	ans = 0
	for (i, j) in h.items():
		if j % 2 == 0:
			ans += len(i) ** 2 * (j // 2)
		else:
			ans += len(i) ** 2 * (j // 2)
			words.append(i)
	my_array = []
	for i in range(len(words)):
		for j in range(len(words)):
			if i != j:
				res = fun(words[i], words[j])
				if res > 0:
					my_array.append((res, words[i], words[j]))
	my_array.sort(key=lambda x: x[0], reverse=True)
	final_ans = set()
	for word in my_array:
		if word[1] not in final_ans and word[2] not in final_ans:
			ans += word[0] ** 2
			final_ans.add(word[1])
			final_ans.add(word[2])
	print(ans, end='\n')


def reverse(s):
	str = ''
	for i in s:
		str = i + str
	return str

def solve():
	n = int(input())
	arr = list()
	num = list()
	num.append(0)
	for i in range(n):
		temp = ''
		temp1 = input()
		temp2 = reverse(temp1)
		for i in range(len(temp1)):
			temp = temp + temp1[i]
			temp = temp + temp2[i]
		arr.append(temp)
	arr.sort()
	for i in range(0, n - 1):
		counter = 0
		a = len(arr[i])
		b = len(arr[i + 1])
		for j in range(min(a, b)):
			if arr[i][j] == arr[i + 1][j]:
				counter += 1
			else:
				break
		counter = int(counter / 2)
		num.append(counter * counter)
	num.append(0)
	answer = 0
	while len(num) > 2:
		if len(num) == 3:
			answer += num[1]
			num.clear()
			break
		else:
			i = 1
			while i < len(num) - 1:
				if num[i] >= num[i - 1] and num[i] >= num[i + 1]:
					answer += num[i]
					num[i - 1] = min(num[i - 1], num[i + 1])
					del num[i:i + 2]
					i -= 1
				i += 1
	print(answer)
t = int(input())
for i in range(t):
	solve()


t = int(input())
L_final = []

def final_string(string):
	b = ''
	for i in range(len(string)):
		b += string[i] + string[-i - 1]
	return b
for i in range(t):
	n = int(input())
	values = []
	for j in range(n):
		values += [final_string(input())]
	values.sort()
	if n > 10 ** 3:
		k = 0
		count = 0
		while k < n - 1:
			t = k
			while t < n - 1 and values[t][0] == values[t + 1][0]:
				t += 1
			L = values[k:t + 1]
			w = t - k + 1
			if w == 1:
				k += 1
				continue
			elif w == 2:
				x = 1
				while x < min(len(L[0]), len(L[1])) and L[0][x] == L[1][x]:
					x += 1
				x = x // 2
				count += x ** 2
				k += 2
				continue
			elif w == 3:
				(x, y) = (1, 1)
				while x < min(len(L[0]), len(L[1])) and L[0][x] == L[1][x]:
					x += 1
				while y < min(len(L[1]), len(L[2])) and L[1][y] == L[2][y]:
					y += 1
				count += max(x // 2, y // 2) ** 2
				k += 3
				continue
			else:
				while len(L) >= 4:
					(x, y, z) = (1, 1, 1)
					while x < min(len(L[0]), len(L[1])) and L[0][x] == L[1][x]:
						x += 1
					while y < min(len(L[1]), len(L[2])) and L[1][y] == L[2][y]:
						y += 1
					(x, y) = (x // 2, y // 2)
					if x > y:
						count += x ** 2
						del L[0]
						del L[0]
						continue
					else:
						while z < min(len(L[2]), len(L[3])) and L[2][z] == L[3][z]:
							z += 1
						z = z // 2
						if y >= z:
							count += y ** 2
							del L[1]
							del L[1]
						else:
							count += x ** 2
							del L[0]
							del L[0]
				if len(L) == 2:
					x = 1
					while x < min(len(L[0]), len(L[1])) and L[0][x] == L[1][x]:
						x += 1
					x = x // 2
					count += x ** 2
					k += w
					continue
				else:
					(x, y) = (1, 1)
					while x < min(len(L[0]), len(L[1])) and L[0][x] == L[1][x]:
						x += 1
					while y < min(len(L[1]), len(L[2])) and L[1][y] == L[2][y]:
						y += 1
					(x, y) = (x // 2, y // 2)
					count += max(x, y) ** 2
					k += w
					continue
			k = t + 1
		L_final += [count]
	else:
		k = 0
		count = 0
		while k < n - 1:
			t = k
			while t < n - 1 and values[t][0] == values[t + 1][0]:
				t += 1
			L = values[k:t + 1]
			while len(L) > 1:
				L1 = []
				for z in range(len(L) - 1):
					x = 1
					while x < min(len(L[z]), len(L[z + 1])) and L[z][x] == L[z + 1][x]:
						x += 1
					L1 += [x]
				L1 = list(map(lambda x: x // 2, L1))
				index_ = L1.index(max(L1))
				count += max(L1) ** 2
				del L[index_]
				del L[index_]
			k = t + 1
		L_final += [count]
for ele in L_final:
	print(ele)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

class Trie:

	def __init__(self, n):
		self.nodes = 1
		self.child = [[0] * 676 for _ in range(n + 1)]
		self.count = [0] * (n + 1)

	def insert(self, word):
		u = 0
		for i in word:
			if not self.child[u][i]:
				self.child[u][i] = self.nodes
				self.nodes += 1
			u = self.child[u][i]
		self.count[u] += 1

	def dfs(self, root, depth=0):
		ans = 0
		for v in range(676):
			if self.child[root][v]:
				ans += self.dfs(self.child[root][v], depth + 1)
				self.count[root] += self.count[self.child[root][v]]
		while self.count[root] >= 2:
			self.count[root] -= 2
			ans += depth ** 2
		return ans
t = int(input())
queries = []
while t > 0:
	t -= 1
	n = int(input())
	s = []
	for i in range(n):
		s.append(input().strip())
	queries.append(s)
ans = []

def convert_string_to_int(s, r):
	res = []
	for i in range(len(s)):
		res.append((ord(s[i]) - ord('a')) * 26 + (ord(r[i]) - ord('a')))
	return res
for i in queries:
	trie = Trie(sum((len(j) for j in i)))
	for j in i:
		res = convert_string_to_int(j, j[::-1])
		trie.insert(res)
	print(trie.dfs(0))


def clean(a):
	required = 0
	length = len(a)
	temp = []
	for i in range(length - 1):
		if a[i][0] == a[i + 1][0]:
			temp.append(a[i])
		else:
			temp.append(a[i])
			if len(temp) > 1:
				required += solve(temp)
			temp = []
	i += 1
	temp.append(a[i])
	if len(temp) > 1:
		required += solve(temp)
	return required

def calculate(a, b):
	index = 0
	la = len(a)
	lb = len(b)
	while index < len(a) and index < len(b):
		c1 = a[index]
		c2 = b[index]
		if c1 == c2:
			index += 1
		else:
			break
	index = index // 2
	return index * index

def solve(arr):
	i = 0
	answer = 0
	length = len(arr)
	used = [0] * length
	que = [i for i in range(length)]
	count = length
	if length == 2:
		return calculate(arr[0], arr[1])
	else:
		head = que[0]
		while True:
			while used[i] != 0:
				i += 1
				i = i % length
			first = i
			i = (i + 1) % length
			while used[i] != 0:
				i += 1
				i = i % length
			second = i
			i = (i + 1) % length
			while used[i] != 0:
				i += 1
				i = i % length
			third = i
			one = calculate(arr[first], arr[second])
			two = calculate(arr[second], arr[third])
			if one >= two:
				answer += one
				used[first] = 1
				used[second] = 1
				que.remove(first)
				que.remove(second)
				count -= 2
				head = que[0]
				i = head
			else:
				i = first + 1
				i = i % length
			if count <= 2:
				break
		if count == 2:
			while used[i] != 0:
				i += 1
				i = i % length
			first = i
			i = (i + 1) % length
			while used[i] != 0:
				i += 1
			second = i
			answer += calculate(arr[first], arr[second])
		return answer
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		s = input()
		print(0)
		continue
	verse = []
	answer = 0
	q = 0
	for _ in range(n):
		s = input()
		rev = s[::-1]
		news = ''
		for i in range(len(s)):
			news += s[i] + rev[i]
		if news in verse:
			verse.remove(news)
			answer += pow(len(news) // 2, 2)
			continue
		verse.append(news)
	verse.sort()
	if len(verse) > 1:
		q = clean(verse)
	print(answer + q)


t = int(input())
for _ in range(t):
	ls = []
	n = int(input())
	for _ in range(n):
		s = input()
		ls.append(s)
	sum = 0
	i = 0
	ans = []
	ls.sort()
	new_ls = []
	count = 0
	for i in range(n):
		if i == 0:
			count += 1
			if i == n - 1:
				sum += len(ls[i]) ** 2 * (count // 2)
				if count % 2 != 0:
					new_ls.append(ls[i])
		elif ls[i] == ls[i - 1]:
			count += 1
			if i == n - 1:
				sum += len(ls[i]) ** 2 * (count // 2)
				if count % 2 != 0:
					new_ls.append(ls[i])
		else:
			sum += len(ls[i - 1]) ** 2 * (count // 2)
			if count % 2 != 0:
				new_ls.append(ls[i - 1])
			count = 1
			if i == n - 1:
				sum += len(ls[i]) ** 2 * (count // 2)
				if count % 2 != 0:
					new_ls.append(ls[i])
	xx = len(new_ls)
	for i in range(xx - 1):
		for j in range(i + 1, xx):
			s1 = new_ls[i]
			s2 = new_ls[j]
			len1 = len(s1)
			len2 = len(s2)
			pre = 0
			l1 = 0
			l2 = 0
			while l1 < len1 and l2 < len2 and (s1[l1] == s2[l2]):
				l2 += 1
				l1 += 1
				pre += 1
			l1 = len1 - 1
			l2 = len2 - 1
			suff = 0
			if pre > 0:
				while l1 >= 0 and l2 >= 0 and (s1[l1] == s2[l2]):
					l1 -= 1
					l2 -= 1
					suff += 1
				maa = min(pre, suff) ** 2
				ans.append([maa, s1, s2])
	x1 = set()
	ans.sort(reverse=True)
	rr = len(ans)
	i = 0
	while i < rr and ans[i][0] > 0:
		if ans[i][1] not in x1 and ans[i][2] not in x1:
			sum += ans[i][0]
			x1.add(ans[i][1])
			x1.add(ans[i][2])
		i += 1
	print(sum)


from sys import stdin

class Box:

	def __init__(self, humt):
		self.humeighumt = humt
		self.link = {}
		self.branchum = 0

def solution(N, W):
	root = Box(0)
	temporary = root
	(hum, p, rem) = (None, None, None)
	countt = 0
	prefix = {}
	for i in range(N):
		w = W[i]
		idn = i + 1
		temporary = root
		for j in range(len(w)):
			s = w[j]
			if s not in temporary.link:
				hum = Box(temporary.humeighumt + 1)
				temporary.link[s] = hum
				temporary = hum
				countt += 1
				temporary.branchum = countt
			else:
				temporary = temporary.link[s]
			if temporary.humeighumt not in prefix:
				prefix[temporary.humeighumt] = {}
			p = prefix[temporary.humeighumt]
			s = s + str(temporary.branchum)
			if s in p:
				p[s].add(idn)
			else:
				p[s] = {idn}
	suffix = {}
	roots = Box(0)
	temporary = roots
	for i in range(N):
		w = W[i]
		idn = i + 1
		temporary = roots
		for j in range(len(w) - 1, -1, -1):
			s = w[j]
			if s not in temporary.link:
				hum = Box(temporary.humeighumt + 1)
				temporary.link[s] = hum
				temporary = hum
				countt += 1
				temporary.branchum = countt
			else:
				temporary = temporary.link[s]
			if temporary.humeighumt not in suffix:
				suffix[temporary.humeighumt] = {}
			p = suffix[temporary.humeighumt]
			s = s + str(temporary.branchum)
			if s in p:
				p[s].add(idn)
			else:
				p[s] = {idn}
	suffix_m = {}
	for num in suffix.keys():
		mp = suffix_m[num] = {}
		for ky in suffix[num].keys():
			for p in suffix[num][ky]:
				mp[p] = ky
	hum = list(prefix.keys())
	hum.sort(reverse=True)
	done = set()
	ans = 0
	for num in hum:
		for ky in prefix[num].keys():
			g = {}
			for p in prefix[num][ky]:
				if p in done:
					continue
				if suffix_m[num][p] in g:
					ans += num ** 2
					done.add(p)
					done.add(g[suffix_m[num][p]])
					del g[suffix_m[num][p]]
				else:
					g[suffix_m[num][p]] = p
	print(ans)

def rajiv():
	read = stdin.readline
	for _ in range(int(read())):
		num = int(read())
		work = [read().strip() for i in range(num)]
		solution(num, work)
rajiv()


class Node(object):

	def __init__(self, cho: str):
		self.cho = cho
		self.childr = []
		self.lev = 0
		self.counter = set()

def addition(root, verb, i):
	node = root
	l = 0
	for cho in verb:
		l += 1
		found = False
		for child in node.childr:
			if child.cho == cho:
				child.counter.add(i)
				node = child
				found = True
				break
		if found == False:
			ne = Node(cho)
			node.childr.append(ne)
			node.childr[-1].counter.add(i)
			ne.lev = l
			node = ne

def final(ilish, l, lor, mim):
	sc = 0
	ta = 0
	i = ilish
	while i > 0:
		for j in l[i]:
			for z in lor[i]:
				op = j & z
				cize = 0
				for k in op:
					if mim[k] == 0:
						cize += 1
						ta = k
						mim[k] = 1
				if cize % 2 == 0:
					sc = sc + cize / 2 * i ** 2
				else:
					sc = sc + int(cize / 2) * i ** 2
					mim[ta] = 0
		i = i - 1
	return int(sc)
for i in range(int(input())):
	st = []
	n = int(input())
	r1 = Node('$')
	r2 = Node('$')
	for j in range(n):
		dws = input()
		st.append(dws)
		rev = st[-1]
		addition(r2, rev[::-1], j)
		addition(r1, rev, j)
	lor = []
	lor.append([])
	q2 = []
	q2 = [r2]
	while len(q2) != 0:
		node = q2[0]
		q2.pop(0)
		for i in node.childr:
			cn = i.counter
			if len(cn) >= 9 - 7:
				if i.lev + 1 > len(lor):
					lor.append([])
				lor[i.lev].append(cn)
				q2.append(i)
	q = [r1]
	l = []
	l.append([])
	while len(q) > 0:
		node = q[0]
		q.pop(0)
		for iny in node.childr:
			cn2 = iny.counter
			if len(cn2) >= 8 - 6:
				if iny.lev + 1 > len(l):
					l.append([])
				l[iny.lev].append(cn2)
				q.append(iny)
	ilish = min(len(l), len(lor)) - 1
	mim = []
	w = len(st)
	for j in range(w):
		mim.append(0)
	answer = final(ilish, l, lor, mim)
	print(answer)


total = input()
total = int(total)
for test in range(total):
	wrd_ = []
	my_dic = {}
	hgt = 0
	wrd_len = []
	numb = input()
	grp = {}
	numb = int(numb)
	for ind in range(numb):
		wrd_.append(input())
		wrd_len.append(len(wrd_[ind]))
	mlen = max(wrd_len)
	for index in range(len(wrd_)):
		wrd_[index] = wrd_[index] + '`' * (mlen - len(wrd_[index]))
	for ind in range(len(wrd_)):
		grp[wrd_[ind], hgt] = 0
	for p in range(mlen):
		gp = 1
		for it in range(len(wrd_)):
			cnt = p
			if my_dic.get((wrd_[it][p], wrd_[it][wrd_len[it] - p - 1], cnt, grp[wrd_[it], hgt])) != None:
				my_dic[wrd_[it][p], wrd_[it][wrd_len[it] - p - 1], cnt, grp[wrd_[it], hgt]].append(wrd_[it])
				grp[wrd_[it], hgt + 1] = grp[my_dic[wrd_[it][p], wrd_[it][wrd_len[it] - p - 1], cnt, grp[wrd_[it], hgt]][0], hgt + 1]
			else:
				my_dic[wrd_[it][p], wrd_[it][wrd_len[it] - p - 1], cnt, grp[wrd_[it], hgt]] = [wrd_[it]]
				grp[wrd_[it], hgt + 1] = gp
				gp += 1
		hgt += 1
	fin = {}
	plus = []
	for h in range(hgt, -1, -1):
		new_d = {}
		for idn in range(numb):
			if fin.get((wrd_[idn], idn)) != None:
				pass
			elif new_d.get(grp[wrd_[idn], h]) != None:
				plus.append(wrd_[idn])
				fin[wrd_[idn], idn] = 1
				plus.append(new_d[grp[wrd_[idn], h]][0][0])
				fin[new_d[grp[wrd_[idn], h]][0]] = 1
				del new_d[grp[wrd_[idn], h]]
			else:
				new_d[grp[wrd_[idn], h]] = [(wrd_[idn], idn)]
	result = 0
	for item in range(0, len(plus), 2):
		str1 = plus[item].strip('`')
		str2 = plus[item + 1].strip('`')
		count = 0
		mini = min(len(str1), len(str2))
		for c in range(mini):
			if str1[c] != str2[c] or str1[-(c + 1)] != str2[-(c + 1)]:
				break
			else:
				count += 1
		result = result + count ** 2
	print(result)


import sys
from random import choice, randint
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

def LI():
	return list(map(int, inp().strip().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	alphasize = 26

	class TNode:

		def __init__(self):
			self.children = [None] * alphasize
			self.l = []
			self.isendofword = False

	def chartoidx(ch):
		return ord(ch) - ord('a')

	def Pinsert(root, s, sidx):
		ptemp = root
		ln = len(s)
		for i in range(ln):
			idx = chartoidx(s[i])
			if not ptemp.children[idx]:
				ptemp.children[idx] = TNode()
			ptemp = ptemp.children[idx]
			ptemp.l.append(sidx)
		ptemp.isendofword = True

	def Sinsert(root, s, sidx):
		stemp = root
		ln = len(s)
		for i in range(ln - 1, -1, -1):
			idx = chartoidx(s[i])
			if not stemp.children[idx]:
				stemp.children[idx] = TNode()
			stemp = stemp.children[idx]
			stemp.l.append(sidx)
		stemp.isendofword = True

	def comb(d, ptr, deep, wordlist, ans, f):
		n = len(ptr.l)
		c = 0
		for i in range(alphasize):
			if ptr.children[i]:
				c += 1
		if c > 1 or (ptr.isendofword and len(ptr.l) > 1):
			if n > 1000:
				d = dict()
				a = []
				for j in range(len(wordlist)):
					w = wordlist[j]
					while len(w) > 0:
						if w not in d:
							d[w] = 1
						else:
							d[w] += 1
						if d[w] == 1:
							a.append(w)
						w = w[:-1]
						if len(w) < 1:
							break
				a.sort()
				res = 0
				for j in range(len(a) - 1, -1, -1):
					if d[a[j]] > 1:
						res += len(a[j]) * len(a[j]) * (d[a[j]] // 2)
					red = d[a[j]] - d[a[j]] % 2
					nw = a[j]
					while len(nw) > 0:
						d[nw] -= red
						nw = nw[:-1]
						if len(nw) < 1:
							break
				ans[0] = res
				f[0] = 1
				return
			else:
				for i in range(n):
					for j in range(i + 1, n):
						d[ptr.l[i], ptr.l[j]] = deep
		for i in range(alphasize):
			if ptr.children[i]:
				comb(d, ptr.children[i], deep + 1, wordlist, ans, f)

	def cmp(x, y):
		return (x > y) - (x < y)

	def compare(a, b):
		if a[1][1] == b[1][1]:
			if a[1][0] == b[1][0]:
				return cmp(a[0], b[0])
			else:
				return cmp(a[1][0], b[1][0])
		else:
			return cmp(a[1][1], b[1][1])
	from functools import cmp_to_key
	import string
	t = I()
	l = []
	for _ in range(t):
		n = I()
		(wordlist, ans, f) = ([], [0], [0])
		for i in range(n):
			w = S()
			wordlist.append(w)
		proot = TNode()
		sroot = TNode()
		for i in range(n):
			Pinsert(proot, wordlist[i], i)
		for i in range(n):
			Sinsert(sroot, wordlist[i], i)
		pred = dict()
		sufd = dict()
		for i in range(alphasize):
			if proot.children[i]:
				comb(pred, proot.children[i], 1, wordlist, ans, f)
		if f[0] == 1:
			l.append(ans[0])
		else:
			for i in range(alphasize):
				if sroot.children[i]:
					comb(sufd, sroot.children[i], 1, wordlist, ans, f)
			pairs = []
			for i in pred:
				if (i[0], i[1]) in sufd:
					d1 = min(pred[i], sufd[i[0], i[1]])
				else:
					d1 = min(pred[i], 0)
				pairs.append([i[0], [i[1], d1]])
			pairs = sorted(pairs, key=cmp_to_key(compare))
			vis = [0 for i in range(n)]
			res = 0
			for i in range(len(pairs) - 1, -1, -1):
				if vis[pairs[i][0]] == False and vis[pairs[i][1][0]] == False:
					res += pairs[i][1][1] * pairs[i][1][1]
					vis[pairs[i][0]] = 1
					vis[pairs[i][1][0]] = 1
			l.append(res)
	for i in range(t):
		pf(str(l[i]))
main()


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return input()
t1 = ii()
while t1:
	t1 -= 1
	n = ii()
	m = {}
	ans = 0
	m1 = {}
	for i in range(n):
		s = si()
		if s not in m:
			m[s] = 1
		else:
			m[s] += 1
		m1[s] = 0
	b = []
	for i in m.keys():
		if m[i] >= 2:
			x = len(i)
			ans += pow(x, 2) * (m[i] // 2)
			if m[i] % 2:
				b.append(i)
		else:
			b.append(i)
	n1 = len(b)
	x = []
	for i in range(n1):
		for j in range(n1):
			if i != j:
				c = 0
				a1 = len(b[i]) - 1
				a2 = len(b[j]) - 1
				l = 0
				t = min(a1, a2)
				r = t
				while l <= t and r >= 0 and (b[i][l] == b[j][l]) and (b[i][a1] == b[j][a2]):
					c += 1
					l += 1
					a1 -= 1
					a2 -= 1
					r -= 1
				if c > 0:
					y = []
					y.append(c)
					y.append(b[i])
					y.append(b[j])
					x.append(y)
	x.sort(reverse=True)
	for i in range(len(x)):
		c = x[i][0]
		s1 = x[i][1]
		s2 = x[i][2]
		if m1[s1] == 0 and m1[s2] == 0:
			ans += pow(c, 2)
			m1[s1] = 1
			m1[s2] = 1
	print(ans)


import math
from itertools import *
from collections import *
from random import shuffle

def prefix(s1, s2):
	c = 0
	while True:
		try:
			if s1[c] != s2[c]:
				break
		except:
			break
		c += 1
	return c

def idea(lis):
	mylis = []
	it = 0
	comb = 0
	for i in lis:
		mylis.append([i, it])
		it += 1
	ready = []
	for i in combinations(mylis, 2):
		ready.append([min(prefix(i[0][0], i[1][0]), prefix(i[0][0][::-1], i[1][0][::-1])), [i[0][1], i[1][1]]])
	ready.sort(key=lambda x: x[0])
	ready = ready[::-1]
	pure = set()
	for i in ready:
		if i[1][0] not in pure and i[1][1] not in pure:
			pure.add(i[1][0])
			pure.add(i[1][1])
			comb += i[0] ** 2
	return comb
for _ in range(int(input())):
	checker = set()
	n = int(input())
	mlis = []
	tot = 0
	lis = []
	for i in range(n):
		s = input()
		mlis.append(s)
	for (i, j) in Counter(mlis).items():
		if j == 1:
			lis.append(i)
		elif j % 2:
			lis.append(i)
			tot += len(i) ** 2 * (j // 2)
		else:
			tot += len(i) ** 2 * (j // 2)
	alpha = defaultdict(list)
	for i in lis:
		alpha[i[0]].append(i)
	for (i, j) in alpha.items():
		sample = [k for k in j]
		shuf = idea(sample)
		tot += shuf
	tot1 = tot
	alpha = defaultdict(list)
	tot = 0
	for i in lis:
		alpha[i[-1]].append(i)
	for (i, j) in alpha.items():
		sample = [k for k in j]
		shuf = idea(sample)
		tot += shuf
	print(max(tot1, tot))


def comp(s1, s2):
	n1 = len(s1)
	n2 = len(s2)
	st = 0
	count = 0
	while st < n1 and st < n2 and (s1[st] == s2[st]) and (s1[n1 - st - 1] == s2[n2 - st - 1]):
		count += 1
		st += 1
	return count

def count(arr):
	n = len(arr)
	d = {arr[i]: 0 for i in range(n)}
	d_str = {}
	for i in range(n):
		if not d[arr[i]]:
			d[arr[i]] += 1
			for j in range(i + 1, n):
				if d_str.get((arr[i], arr[j])) == None and d_str.get((arr[j], arr[i])) == None:
					val = comp(arr[i], arr[j]) ** 2
					d_str[arr[i], arr[j]] = val
		else:
			d[arr[i]] += 1
	final = sorted(d_str.items(), key=lambda x: x[1], reverse=True)
	val = 0
	for pair in final:
		if pair[1] == 0:
			return val
		a = pair[0][0]
		b = pair[0][1]
		if d[a] > 0 and d[b] > 0:
			while d[a] > 0 and d[b] > 0:
				d[a] -= 1
				d[b] -= 1
				found = 0
				if d[a] >= 0 and d[b] >= 0:
					found = 1
					val += pair[1]
				if not found:
					d[a] += 1
					d[b] += 1
					break
	return val
t = int(input())
for _ in range(t):
	n = int(input())
	lis = []
	for i in range(n):
		lis.append(input())
	print(count(lis))


for t in range(int(input())):
	n = int(input())
	li2 = []
	for i in range(n):
		li2 += [input()]
	li3 = list(set(li2))
	(ans, li) = (0, [])
	for x in li3:
		ct = li2.count(x)
		if ct % 2 != 0:
			li += [x]
			ct -= 1
		ans += ct // 2 * len(x) ** 2
	li.sort()
	(i, j) = (0, 1)
	n = len(li)
	while j < n:
		while j < n and li[i][0] == li[j][0]:
			j += 1
		temp = li[i:j]
		i = j
		j += 1
		nx = len(temp)
		if nx > 2:
			marr = []
			for ii in range(1, nx):
				x = temp[ii]
				for jj in range(ii):
					y = temp[jj]
					l = min(len(y), len(x))
					ctr = 0
					while ctr < l and x[ctr] == y[ctr] and (x[-1 - ctr] == y[-1 - ctr]):
						ctr += 1
					if ctr != 0:
						marr += [[ctr, ii, jj]]
			marr.sort(reverse=True)
			done = [1 for ii in range(nx)]
			val = 0
			for itm in marr:
				(x, ii, jj) = itm
				if x == 0:
					break
				if done[ii] and done[jj]:
					val += x ** 2
					done[ii] = 0
					done[jj] = 0
			ans += val
		elif nx == 2:
			(x, y) = (temp[0], temp[1])
			l = min(len(y), len(x))
			ctr = 0
			while ctr < l and x[ctr] == y[ctr] and (x[-1 - ctr] == y[-1 - ctr]):
				ctr += 1
			ans += ctr ** 2
	print(ans)


import operator
t = input()
t = int(t)
for test_cases in [i for i in list(range(t))]:
	n = int(input())
	the_given_strings = []
	for i in range(n):
		the_given_strings.append(input())
	to_remove_common_elements = {}
	for i in the_given_strings:
		if to_remove_common_elements.get(i) != None:
			to_remove_common_elements[i] += 1
		else:
			to_remove_common_elements[i] = 1
	final_result = 0
	the_given_strings = []
	for (i, j) in to_remove_common_elements.items():
		if j >= 2:
			temp = i
			temp2 = j // 2
			if j - 2 * temp2 != 0:
				the_given_strings.append(i)
			final_result += pow(len(temp), 2) * temp2
		else:
			the_given_strings.append(i)
	number = len(the_given_strings)
	temporary_array = []
	for i in range(number):
		for j in range(number):
			if i != j:
				string1 = the_given_strings[i]
				string2 = the_given_strings[j]
				len_string1 = len(the_given_strings[i])
				len_string2 = len(the_given_strings[j])
				upto = min(len_string1, len_string2)
				end = -1
				start = 0
				inner_cnt = 0
				while start < upto and end >= -upto and (string1[start] == string2[start]) and (string1[end] == string2[end]):
					inner_cnt += 1
					start += 1
					end -= 1
				if inner_cnt == 0:
					pass
				else:
					temporary_array.append((inner_cnt, the_given_strings[i], the_given_strings[j]))
	temporary_array = sorted(temporary_array, key=operator.itemgetter(0), reverse=True)
	final_dictionary = dict()
	for item in temporary_array:
		if final_dictionary.get(item[1]) == None:
			if final_dictionary.get(item[2]) == None:
				final_result += pow(item[0], 2)
				final_dictionary[item[1]] = 1
				final_dictionary[item[2]] = 1
	print(final_result)


t = int(input())
for t in range(t):
	for i in range(1000):
		continue
	times = int(input())
	p = []
	for i in range(times):
		p.append(input().strip())
	vect = [False] * times
	p.sort()
	rt = 0
	left = 0
	while left < times - 1:
		if p[left] == p[left + 1]:
			lq = len(p[left])
			rt += lq ** 2
			vect[left] = True
			left += 1
			vect[left] = True
		left += 1
	tm = {}
	for it in range(times):
		if vect[it]:
			continue
		pehle = ''
		baad = ''
		wt = p[it]
		por = len(wt)
		trr = por - 1
		ytl = 0
		while ytl < por and trr >= 0:
			pehle += wt[ytl]
			baad = wt[trr] + baad
			te = (pehle, baad, len(pehle))
			if te in tm:
				tm[te].append([len(pehle), it])
			else:
				tm[te] = [[len(pehle), it]]
			ytl += 1
			trr -= 1
	cess = [rq for (nw, rq) in sorted(tm.items(), key=lambda item: item[1][0], reverse=True)]
	for y in cess:
		if len(y) <= 1:
			continue
		else:
			nt = 0
			rta = []
			for i in y:
				if vect[i[1]]:
					continue
				else:
					nt += 1
					rta.append(i[1])
			if nt > 1:
				rt += y[0][0] ** 2 * (nt // 2)
				if nt % 2 == 1:
					for i in range(len(rta) - 1):
						vect[rta[i]] = True
				else:
					for i in rta:
						vect[i] = True
	print(rt)


import sys
import time
ALPHA = ['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']

def n_after2(string, d):
	n = 0
	for i in ALPHA:
		search = string + i
		if search in d:
			n += d[search]
	return n

def give_result2(arr):
	res = 0
	d = {}
	for ele in arr:
		string = ''
		for char in ele:
			string += char
			if string in d:
				d[string] += 1
			else:
				d[string] = 1
	for ele in arr:
		if d[ele] == 0:
			continue
		string = ''
		c = 0
		for x in range(len(ele)):
			string += ele[x]
			cnt = d[string]
			if cnt == 1:
				prev = string[-1]
				string = string[:-1]
				break
			c += 1
		if c == len(ele):
			prev = '$'
		if string == '':
			res += 0
			continue
		if d[string] - n_after2(string, d) >= 2:
			res += c ** 2
			s = ''
			for char in ele:
				s += char
				d[s] -= 2
		else:
			f = False
			while string != '' and (not f):
				for i in ALPHA:
					char = i
					s = string + char
					if char != prev and s in d and (d[s] > 0) and (d[s] % 2 != 0):
						string += char
						f = True
						break
				if not f:
					c -= 1
					prev = string[-1]
					string = string[:-1]
				else:
					while n_after2(string, d) % 2 == 1:
						for i in ALPHA:
							char = i
							s = string + char
							if s in d and d[s] > 0 and (d[s] % 2 != 0):
								string += char
								break
			if string != '':
				s = ''
				for char in ele:
					s += char
					d[s] -= 1
				s = ''
				for char in string:
					s += char
					d[s] -= 1
				res += c ** 2
			else:
				res += 0
	return res

def give_result3(arr, f_strings):
	res = 0
	d = f_strings
	for ele in arr:
		if d[ele] == 0:
			continue
		string = ''
		c = 0
		for x in range(len(ele)):
			string += ele[x]
			cnt = d[string]
			if cnt == 1:
				prev = string[-1]
				string = string[:-1]
				break
			c += 1
		if c == len(ele):
			prev = '$'
		if string == '':
			res += 0
			continue
		if d[string] - n_after2(string, d) >= 2:
			res += c ** 2
			s = ''
			for char in ele:
				s += char
				d[s] -= 2
		else:
			f = False
			while string != '' and (not f):
				for i in ALPHA:
					char = i
					s = string + char
					if char != prev and s in d and (d[s] > 0) and (d[s] % 2 != 0):
						string += char
						f = True
						break
				if not f:
					c -= 1
					prev = string[-1]
					string = string[:-1]
				else:
					while n_after2(string, d) % 2 == 1:
						for i in ALPHA:
							char = i
							s = string + char
							if s in d and d[s] > 0 and (d[s] % 2 != 0):
								string += char
								break
			if string != '':
				s = ''
				for char in ele:
					s += char
					d[s] -= 1
				s = ''
				for char in string:
					s += char
					d[s] -= 1
				res += c ** 2
			else:
				res += 0
	return res

def n_after(fw_string, bw_string, d, f_strings):
	n = 0
	for i in ALPHA:
		s1 = fw_string + i
		if s1 not in f_strings:
			continue
		for j in ALPHA:
			search = ''.join([s1, ':', bw_string, j])
			if search in d:
				n += d[search]
	return n

def give_result(arr, t0):
	res = 0
	d = {}
	d2 = {}
	f_strings = {}
	used = {}
	for ele in arr:
		if ele in used:
			used[ele] += 1
		else:
			used[ele] = 1
		fw_string = ''
		bw_string = ''
		for x in range(len(ele)):
			fw_string += ele[x]
			bw_string += ele[len(ele) - x - 1]
			if fw_string in f_strings:
				f_strings[fw_string] += 1
			else:
				f_strings[fw_string] = 1
			rez = ':'.join([fw_string, bw_string])
			if rez in d:
				d[rez] += 1
			else:
				d[rez] = 1
	t1 = time.time()
	if t1 - t0 >= 6.0 and t1 - t0 <= 6.5:
		return give_result3(arr, f_strings)
	for ele in arr:
		if used[ele] == 0:
			continue
		fw_string = ''
		bw_string = ''
		c = 0
		for x in range(len(ele)):
			fw_string += ele[x]
			bw_string += ele[len(ele) - x - 1]
			cnt = d[fw_string + ':' + bw_string]
			if cnt == 1:
				prev = fw_string[-1] + ':' + bw_string[-1]
				fw_string = fw_string[:-1]
				bw_string = bw_string[:-1]
				break
			c += 1
		if c == len(ele):
			prev = '$'
		if len(fw_string) == 0 or len(bw_string) == 0:
			res += 0
			continue
		if d[fw_string + ':' + bw_string] - n_after(fw_string, bw_string, d, f_strings) >= 2:
			res += c ** 2
			s = ''
			r = ''
			for x in range(len(ele)):
				s += ele[x]
				r += ele[len(ele) - x - 1]
				d[s + ':' + r] -= 2
			used[ele] -= 2
		else:
			f = False
			while (len(fw_string) != 0 and len(bw_string) != 0) and (not f):
				for i in ALPHA:
					fw_char = i
					s1 = fw_string + fw_char
					if s1 not in f_strings:
						continue
					for j in ALPHA:
						bw_char = j
						s = ''.join([s1, ':', bw_string, bw_char])
						if fw_char + ':' + bw_char != prev and s in d and (d[s] > 0) and (d[s] % 2 != 0):
							fw_string += fw_char
							bw_string += bw_char
							f = True
							break
					if f:
						break
				if not f:
					c -= 1
					prev = ''.join([fw_string[-1], ':', bw_string[-1]])
					fw_string = fw_string[:-1]
					bw_string = bw_string[:-1]
				else:
					while n_after(fw_string, bw_string, d, f_strings) % 2 == 1:
						for i in ALPHA:
							fw_char = i
							s1 = fw_string + fw_char
							if s1 not in f_strings:
								continue
							for j in ALPHA:
								flg = False
								bw_char = j
								s = ''.join([s1, ':', bw_string, bw_char])
								if s in d and d[s] > 0 and (d[s] % 2 != 0):
									fw_string += fw_char
									bw_string += bw_char
									flg = True
									break
							if flg:
								break
			if fw_string + ':' + bw_string != ':':
				s = ''
				r = ''
				for x in range(len(ele)):
					s += ele[x]
					r += ele[len(ele) - x - 1]
					d[s + ':' + r] -= 1
				s = ''
				r = ''
				for x in range(len(fw_string)):
					s += fw_string[x]
					r += bw_string[x]
					d[s + ':' + r] -= 1
				res += c ** 2
				used[ele] -= 1
				used[fw_string] -= 1
			else:
				res += 0
	return res
t0 = time.time()
t = int(sys.stdin.readline())
res = ''
for _ in range(t):
	n = int(sys.stdin.readline())
	flag = False
	strings = []
	lens = 0
	npal = 0
	for i in range(n):
		s = sys.stdin.readline()[:-1]
		lens += len(s)
		if s != s[::-1]:
			flag = True
		else:
			npal += 1
		strings.append(s)
	strings.sort()
	if flag:
		res += str(give_result(strings, t0)) + '\n'
	else:
		res += str(give_result2(strings)) + '\n'
sys.stdout.write(res)


def commonpref(a, k):
	c = 0
	for i in range(k):
		if a[0][i] != a[1][i]:
			break
		c += 1
	return c
T = int(input())
while T > 0:
	N = int(input())
	c = 0
	ai = []
	a = []
	for i in range(N):
		h = input()
		ai.append(h)
	ex = []
	di = {}
	for i in range(N):
		if ai[i] not in di.keys():
			di[ai[i]] = 1
		else:
			di[ai[i]] += 1
	for i in range(N):
		cn = di[ai[i]]
		if cn > 1 and cn % 2 == 0:
			if ai[i] not in ex:
				num = len(ai[i]) * len(ai[i])
				c += num * int(cn / 2)
				ex.append(ai[i])
		elif ai[i] in a and (cn > 1 and cn % 2 != 0):
			bn = int(cn / 2)
			if ai[i] not in ex:
				num = len(ai[i]) * len(ai[i])
				c += num * bn
				ex.append(ai[i])
		else:
			a.append(ai[i])
	keep = []
	ni = len(a)
	if ni > 1:
		for i in range(ni):
			for j in range(i, ni):
				k = min(len(a[i]), len(a[j]))
				if j != i and a[i] == a[j]:
					num = len(a[i]) * len(a[j])
					keep.append([[i, j], num])
				elif j != i and (a[i][0] == a[j][0] and a[i][-1] != a[j][-1]):
					keep.append([[i, j], 0])
				elif j != i and (a[i][0] != a[j][0] and a[i][-1] == a[j][-1]):
					keep.append([[i, j], 0])
				elif j != i and (a[i][0] == a[j][0] and a[i][-1] == a[j][-1]):
					ri = a[i][::-1]
					rj = a[j][::-1]
					if a[i] == ri and a[j] == rj:
						f = commonpref([a[i], a[j]], k)
						num = f * f
						keep.append([[i, j], num])
					else:
						f = commonpref([a[i], a[j]], k)
						g = commonpref([ri, rj], f)
						num = g * g
						keep.append([[i, j], num])
	k1 = sorted(keep, key=lambda x: x[1], reverse=True)
	k3 = []
	for i in range(len(k1)):
		if k1[i][0][0] not in k3 and k1[i][0][1] not in k3:
			c += k1[i][1]
			k3.append(k1[i][0][0])
			k3.append(k1[i][0][1])
	print(c)
	T -= 1


def match(s1, s2):
	(c1, c2) = (0, 0)
	for i in range(min(len(s1), len(s2))):
		if s1[i] != s2[i]:
			break
		else:
			c1 += 1
	s1 = s1[::-1]
	s2 = s2[::-1]
	for i in range(min(len(s1), len(s2))):
		if s1[i] != s2[i]:
			break
		else:
			c2 += 1
	return min(c1, c2) ** 2
t = int(input())
for _ in range(t):
	n = int(input())
	counter = 0
	d = dict()
	for j in range(n):
		string = input()
		m = len(string)
		(pre, suf) = ('', '')
		for i in range(0, m):
			pre = pre + string[i]
			suf = string[m - 1 - i] + suf
			x = (pre, suf, i + 1)
			if x in d:
				d[x].append([i + 1, j])
			else:
				d[x] = [[i + 1, j]]
	l = [i for (key, i) in sorted(d.items(), key=lambda x: x[1][0], reverse=True)]
	c = [False for i in range(n)]
	for i in l:
		if len(i) <= 1:
			continue
		leng = i[0][0]
		ind = 0
		inc = 0
		flag = 0
		incl = []
		for j in i:
			if c[j[1]] == False:
				inc += 1
				incl.append(j[1])
		if inc % 2 != 0:
			del incl[-1]
			inc -= 1
		for j in incl:
			c[j] = True
		inc = int(inc / 2)
		counter += inc * leng ** 2
	print(counter)


from sys import stdin
from collections import defaultdict, OrderedDict
t = int(stdin.readline())
for i in range(t):
	w = int(stdin.readline())
	arr = defaultdict(int)
	for j in range(w):
		word = str(stdin.readline()).rstrip()
		arr[word] = arr[word] + 1
	result = 0
	word_list = []
	for (word, count) in arr.items():
		if count > 1:
			pair_count = int(count / 2)
			result = result + len(word) ** 2 * pair_count
			if pair_count * 2 == count:
				continue
		word_list.append(word)
	n_word = len(word_list)
	distinct_pair = {}
	for x in range(n_word):
		for y in range(x + 1, n_word):
			max_l = min(len(word_list[x]), len(word_list[y]))
			common = 0
			for z in range(max_l):
				neg_z = z * -1 - 1
				if word_list[x][z] != word_list[y][z] or word_list[x][neg_z] != word_list[y][neg_z]:
					break
				common = common + 1
			if common:
				distinct_pair[x, y] = common ** 2
	sorted_dict = OrderedDict(sorted(distinct_pair.items(), key=lambda item: item[1], reverse=True))
	include_list = []
	for (k, v) in sorted_dict.items():
		if k[0] in include_list or k[1] in include_list:
			continue
		result += v
		include_list.append(k[0])
		include_list.append(k[1])
	print(result)


from sys import stdin

class Node:

	def __init__(self, height, chr):
		self.height = height
		self.chr = chr
		self.link = {}
		self.branch = 0

def solve(N, W):
	root = Node(0, '#')
	temp = root
	(h, p, rem) = (None, None, None)
	cnz = 0
	prefix = {}
	for i in range(N):
		w = W[i]
		idn = i + 1
		temp = root
		for j in range(len(w)):
			s = w[j]
			if s not in temp.link:
				h = Node(temp.height + 1, s)
				temp.link[s] = h
				temp = h
				cnz += 1
				temp.branch = cnz
			else:
				temp = temp.link[s]
			if temp.height not in prefix:
				prefix[temp.height] = {}
			p = prefix[temp.height]
			s = s + str(temp.branch)
			if s in p:
				p[s].add(idn)
			else:
				p[s] = {idn}
	suffix = {}
	roots = Node(0, '#s')
	temp = roots
	for i in range(N):
		w = W[i]
		idn = i + 1
		temp = roots
		for j in range(len(w) - 1, -1, -1):
			s = w[j]
			if s not in temp.link:
				h = Node(temp.height + 1, s)
				temp.link[s] = h
				temp = h
				cnz += 1
				temp.branch = cnz
			else:
				temp = temp.link[s]
			if temp.height not in suffix:
				suffix[temp.height] = {}
			p = suffix[temp.height]
			s = s + str(temp.branch)
			if s in p:
				p[s].add(idn)
			else:
				p[s] = {idn}
	suffix_m = {}
	for num in suffix.keys():
		mp = suffix_m[num] = {}
		for ky in suffix[num].keys():
			for p in suffix[num][ky]:
				mp[p] = ky
	h = list(prefix.keys())
	h.sort(reverse=True)
	done = set()
	ans = 0
	for num in h:
		for ky in prefix[num].keys():
			g = {}
			for p in prefix[num][ky]:
				if p in done:
					continue
				if suffix_m[num][p] in g:
					ans += num ** 2
					done.add(p)
					done.add(g[suffix_m[num][p]])
					del g[suffix_m[num][p]]
				else:
					g[suffix_m[num][p]] = p
	print(ans)

def main():
	inp = stdin.readline
	for _ in range(int(inp())):
		N = int(inp())
		W = [inp().strip() for i in range(N)]
		solve(N, W)
main()


from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def match_prefix(s1, s2):
	prefix = 0
	(i, j) = (0, 0)
	while i < len(s1) and j < len(s2):
		if s1[i] == s2[j]:
			i += 1
			j += 1
			prefix += 1
		else:
			break
	return prefix * prefix

def match_suffix(s1, s2):
	suffix = 0
	(i, j) = (len(s1) - 1, len(s2) - 1)
	while i >= 0 and j >= 0:
		if s1[i] == s2[j]:
			i -= 1
			j -= 1
			suffix += 1
		else:
			break
	return suffix * suffix
for _ in range(iinput()):
	n = iinput()
	a = []
	d = defaultdict(int)
	for i in range(n):
		a.append(input())
		d[a[i]] += 1
	result = 0
	for i in d:
		result += len(i) * len(i) * (d[i] // 2)
		d[i] = d[i] % 2
	a = []
	for i in d:
		if d[i] != 0:
			a.append(i)
	a.sort()
	while len(a) > 1:
		(best_s1, best_s2) = ('', '')
		mx = 0
		for i in range(len(a)):
			for j in range(i + 1, len(a)):
				s1 = a[i]
				s2 = a[j]
				prefix = match_prefix(s1, s2)
				suffix = match_suffix(s1, s2)
				if prefix == 0 and suffix == 0:
					break
				ans = min(prefix, suffix)
				if mx <= ans:
					mx = ans
					best_s1 = s1
					best_s2 = s2
		result += mx
		if mx == 0:
			break
		if best_s1 in d:
			d.pop(best_s1)
			a.remove(best_s1)
		if best_s2 in d:
			d.pop(best_s2)
			a.remove(best_s2)
	print(result)


for _ in range(int(input())):
	n = int(input())
	jode = []
	for i in range(n):
		jode.append(input().strip())
	check = [False] * n
	jode.sort()
	ans = 0
	lii = 0
	while lii < n - 1:
		if jode[lii] == jode[lii + 1]:
			ans += len(jode[lii]) ** 2
			check[lii] = True
			check[lii + 1] = True
			lii += 1
		lii += 1
	mt = {}
	for i in range(100):
		continue
	for t in range(n):
		if check[t]:
			continue
		wt = jode[t]
		wor = len(wt)
		l = 0
		r = wor - 1
		prefix = ''
		sufix = ''
		while l < wor and r >= 0:
			prefix += wt[l]
			sufix = wt[r] + sufix
			temp = (prefix, sufix, len(prefix))
			if temp in mt:
				mt[temp].append([len(prefix), t])
			else:
				mt[temp] = [[len(prefix), t]]
			l += 1
			r -= 1
	process = [zen for (ken, zen) in sorted(mt.items(), key=lambda item: item[1][0], reverse=True)]
	for x in process:
		if len(x) <= 1:
			continue
		else:
			count = 0
			a = []
			for i in x:
				if check[i[1]]:
					continue
				else:
					count += 1
					a.append(i[1])
			if count >= 2:
				ans += x[0][0] ** 2 * (count // 2)
				if count % 2 == 0:
					for i in a:
						check[i] = True
				else:
					for i in range(len(a) - 1):
						check[a[i]] = True
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	alc = [0] * n
	st = []
	dict = {}
	for i in range(n):
		st.append(input().strip())
	st.sort()
	ans = 0
	i = 0
	lst = []
	while i < n - 1:
		if st[i] == st[i + 1]:
			ans += len(st[i]) ** 2
			alc[i] = 1
			alc[i + 1] = 1
			i += 1
		i += 1
	for i in range(n):
		if alc[i]:
			alc[i] = 1
		else:
			alc[i] = 0
	for i in range(n):
		if alc[i]:
			continue
		word = st[i]
		w = len(word)
		l = 0
		r = w - 1
		pre = ''
		suf = ''
		while l < w and r >= 0:
			pre += word[l]
			suf = word[r] + suf
			ls = (pre, suf, len(pre))
			if ls in dict:
				dict[ls].append([len(pre), i])
			else:
				dict[ls] = [[len(pre), i]]
			l += 1
			r -= 1
	a = [v for (j, v) in sorted(dict.items(), reverse=True)]
	for i in a:
		if len(i) <= 1:
			continue
		else:
			d = []
			b = 0
			for j in i:
				if alc[j[1]]:
					continue
				else:
					b += 1
					d.append(j[1])
			if b >= 2:
				ans += i[0][0] ** 2 * (b // 2)
				if b % 2 == 0:
					for j in d:
						alc[j] = 1
				else:
					for j in range(len(d) - 1):
						alc[d[j]] = 1
	print(ans)


import heapq

def stanza_beauty(wd1, wd2):
	L = min(len(wd1), len(wd2))
	for i in range(L):
		if wd1[i] != wd2[i] or wd1[-i - 1] != wd2[-i - 1]:
			return i * i
	return L * L

def transform(wd):
	return ''.join((''.join((a, b)) for (a, b) in zip(wd, reversed(wd))))

def solve(N, words):
	words = sorted(words, key=transform)
	nxt = [None for _ in range(N)]
	prv = [None for _ in range(N)]
	stanzas = []
	for i in range(N - 1):
		wd1 = words[i]
		j = i + 1
		wd2 = words[j]
		b = stanza_beauty(wd1, wd2)
		nxt[i] = j
		prv[j] = i
		if b > 0:
			heapq.heappush(stanzas, (-b, i, j))
	solution = 0
	taken = [False for _ in range(N)]
	while stanzas:
		(weight, i, j) = heapq.heappop(stanzas)
		if taken[i] or taken[j]:
			continue
		taken[i] = taken[j] = True
		solution += -weight
		p = prv[i]
		n = nxt[j]
		if p is None or n is None:
			continue
		if p == n:
			continue
		nxt[p] = n
		prv[n] = p
		wd1 = words[p]
		wd2 = words[n]
		b = stanza_beauty(wd1, wd2)
		if b > 0:
			heapq.heappush(stanzas, (-b, p, n))
	return solution

def main():
	import sys
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		words = []
		for _ in range(N):
			words.append(sys.stdin.readline().strip())
		print(solve(N, words))
main()


for _ in range(int(input())):
	n = int(input())
	words = []
	for i in range(n):
		words.append(input().strip())
	done = [False] * n
	words.sort()
	i = 0
	res = 0
	lst = []
	while i < n - 1:
		if words[i] == words[i + 1]:
			res += len(words[i]) ** 2
			done[i] = True
			done[i + 1] = True
			i += 1
		i += 1
	mapp = {}
	for i in range(n):
		if done[i]:
			continue
		word = words[i]
		w = len(word)
		l = 0
		r = w - 1
		pre = ''
		suf = ''
		while l < w and r >= 0:
			pre += word[l]
			suf = word[r] + suf
			ls = (pre, suf, len(pre))
			if ls in mapp:
				mapp[ls].append([len(pre), i])
			else:
				mapp[ls] = [[len(pre), i]]
			l += 1
			r -= 1
	op = [v for (k, v) in sorted(mapp.items(), key=lambda item: item[1][0], reverse=True)]
	for i in op:
		if len(i) <= 1:
			continue
		else:
			cnt = 0
			ld = []
			for k in i:
				if done[k[1]]:
					continue
				else:
					cnt += 1
					ld.append(k[1])
			if cnt >= 2:
				res += i[0][0] ** 2 * (cnt // 2)
				if cnt % 2 == 0:
					for k in ld:
						done[k] = True
				else:
					for k in range(len(ld) - 1):
						done[ld[k]] = True
	print(res)


import copy
import sys
from collections import Counter

def fun(val):
	return
for _ in range(int(input())):
	n = int(input())
	words = []
	for i in range(n):
		words.append(input().strip())
	done = [False] * n
	words.sort()
	i = 0
	res = 0
	lst = []
	while i < n - 1:
		if words[i] == words[i + 1]:
			res += len(words[i]) ** 2
			done[i] = True
			done[i + 1] = True
			i += 1
		i += 1
	mapp = {}
	for i in range(n):
		if done[i]:
			continue
		word = words[i]
		w = len(word)
		l = 0
		r = w - 1
		pre = ''
		suf = ''
		while l < w and r >= 0:
			pre += word[l]
			suf = word[r] + suf
			ls = (pre, suf, len(pre))
			if ls in mapp:
				mapp[ls].append([len(pre), i])
			else:
				mapp[ls] = [[len(pre), i]]
			l += 1
			r -= 1
	op = [v for (k, v) in sorted(mapp.items(), key=lambda item: item[1][0], reverse=True)]
	for i in op:
		if len(i) <= 1:
			continue
		else:
			cnt = 0
			ld = []
			for k in i:
				if done[k[1]]:
					continue
				else:
					cnt += 1
					ld.append(k[1])
			if cnt >= 2:
				res += i[0][0] ** 2 * (cnt // 2)
				if cnt % 2 == 0:
					for k in ld:
						done[k] = True
				else:
					for k in range(len(ld) - 1):
						done[ld[k]] = True
	print(res)


import heapq

def prefixSuffix(s1, s2):
	if s1 == s2:
		return len(s1)
	if s1[len(s1) - 1] != s2[len(s2) - 1]:
		return 0
	pref = 1
	for i in range(1, min(len(s1), len(s2))):
		if s1[i] == s2[i] and s1[len(s1) - 1 - i] == s2[len(s2) - 1 - i]:
			pref += 1
		else:
			break
	return pref

def verse(arr):
	x = []
	l = 0
	visited = [False] * len(arr)
	arr.sort()
	for i in range(len(arr) - 1):
		for j in range(i + 1, len(arr)):
			if arr[i][0] != arr[j][0]:
				break
			if arr[i][len(arr[i]) - 1] != arr[j][len(arr[j]) - 1]:
				continue
			heapq.heappush(x, (-prefixSuffix(arr[i], arr[j]), i, j))
	if len(arr) % 2 != 0:
		l1 = len(arr) - 2
	else:
		l1 = len(arr) - 1
	ans = 0
	while len(x) > 0:
		(y, i, j) = heapq.heappop(x)
		if not (visited[i] or visited[j]):
			ans += y ** 2
			l += 2
			visited[i] = True
			visited[j] = True
		if l == l1:
			break
	return ans
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = set()
		ans = 0
		for i in range(n):
			x = input()
			if x not in arr:
				arr.add(x)
			else:
				arr.remove(x)
				ans += len(x) ** 2
		arr = list(arr)
		print(ans + verse(arr))
except:
	pass


for _ in range(int(input())):
	n = int(input())
	completed = [False] * n
	beauty = 0
	words = []
	for i in range(n):
		words.append(input())
	words.sort()
	for i in range(n - 1):
		if words[i] == words[i + 1] and completed[i] == False and (completed[i + 1] == False):
			beauty += len(words[i]) ** 2
			(completed[i], completed[i + 1]) = (True, True)
	mapping = dict()
	for i in range(n):
		if completed[i] == True:
			continue
		word = words[i]
		(prefix, suffix) = ('', '')
		length = len(word)
		(left, right) = (0, length - 1)
		while left < length and right >= 0:
			prefix = prefix + word[left]
			suffix = word[right] + suffix
			tup = (prefix, suffix, len(prefix))
			if tup in mapping:
				mapping[tup].append([len(prefix), i])
			else:
				mapping[tup] = [[len(prefix), i]]
			left += 1
			right -= 1
	common = [value for (key, value) in sorted(mapping.items(), key=lambda item: item[1][0], reverse=True)]
	for i in common:
		if len(i) > 1:
			count = 0
			included = []
			for j in i:
				if completed[j[1]] == False:
					count += 1
					included.append(j[1])
			if count >= 2:
				beauty += i[0][0] ** 2 * (count // 2)
				if count % 2 == 0:
					for k in included:
						completed[k] = True
				else:
					del included[-1]
					for k in included:
						completed[k] = True
	print(beauty)


def compare(s1, s2):
	pre = 0
	suf = 0
	if s1 == s2:
		return (0, pow(len(s1), 2))
	else:
		s1 = list(s1)
		s2 = list(s2)
		for i in range(min(len(s1), len(s2))):
			if s1[i] == s2[i]:
				pre += 1
			else:
				break
		s1 = s1[::-1]
		s2 = s2[::-1]
		for i in range(min(len(s1), len(s2))):
			if s1[i] == s2[i]:
				suf += 1
			else:
				break
		return (1, min(pow(pre, 2), pow(suf, 2)))

def compare_2(arr, z, start, mi):
	z2 = start
	mi2 = mi
	for i in range(len(arr)):
		if i == start or i == z:
			continue
		else:
			(a2, s2) = compare(arr[z], arr[i])
			if a2 == 0:
				z2 = i
				del arr[z]
				del arr[i - 1]
				mi2 = s2
				return mi2
				break
			elif mi2 < s2:
				z2 = i
				mi2 = s2
	if z2 == start:
		del arr[start]
		del arr[z - 1]
		return mi2
	else:
		return compare_2(arr, z2, z, mi2)
for t in range(int(input())):
	n = int(input())
	arr = []
	total = 0
	mi = 0
	for i in range(n):
		arr.append(input())
	while len(arr) > 1:
		z = 1
		for i in range(1, len(arr)):
			(a, s) = compare(arr[0], arr[i])
			if mi < s:
				z = i
				mi = s
			if a == 0:
				mi = pow(len(arr[0]), 2)
				del arr[0]
				del arr[i - 1]
				i -= 2
				break
			if i == len(arr) - 1 and mi == 0:
				del arr[0]
				i -= 1
				recur = 1
		if a != 0 and mi != 0:
			mi = compare_2(arr, z, 0, mi)
		total += mi
		mi = 0
	print(total)


def solve(arr):
	answer = 0
	while len(arr) >= 2:
		maximum = 0
		word1 = ''
		word2 = ''
		first = 0
		second = 0
		length = len(arr)
		for i in range(length):
			for j in range(i + 1, length):
				first = i
				second = j
				if calculate(arr[first], arr[second]) >= maximum:
					word1 = arr[first]
					word2 = arr[second]
					maximum = calculate(arr[first], arr[second])
		temp = calculate(word1, word2)
		answer += temp
		arr.remove(word1)
		arr.remove(word2)
	return answer

def calculate(a, b):
	index = 0
	la = len(a)
	lb = len(b)
	while index < len(a) and index < len(b):
		c1 = a[index]
		c2 = b[index]
		e1 = a[la - 1 - index]
		e2 = b[lb - 1 - index]
		if c1 == c2 and e1 == e2:
			index += 1
		else:
			break
	return index * index

def clean(a):
	required = 0
	length = len(a)
	temp = []
	for i in range(length - 1):
		if a[i][0] == a[i + 1][0]:
			temp.append(a[i])
		else:
			temp.append(a[i])
			if len(temp) > 1:
				required += solve(temp)
			temp = []
	i += 1
	temp.append(a[i])
	if len(temp) > 1:
		required += solve(temp)
	return required
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		s = input()
		print(0)
		continue
	verse = []
	answer = 0
	q = 0
	for _ in range(n):
		s = input()
		if s in verse:
			verse.remove(s)
			answer += pow(len(s), 2)
			continue
		verse.append(s)
	verse.sort()
	if len(verse) > 1:
		q = clean(verse)
	print(answer + q)


def change(a):
	res = ''
	i = 0
	j = len(a) - 1
	n = len(a)
	for i in range(n):
		res += a[i] + a[n - i - 1]
	return res

def beauty(a, b):
	na = len(a)
	nb = len(b)
	if na <= nb:
		for i in range(na):
			if a[i] != b[i]:
				return i // 2
		return na // 2
	else:
		for i in range(nb):
			if a[i] != b[i]:
				return i // 2
		return nb // 2
t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
	if n == 1:
		print(0)
		continue
	for i in range(n):
		l[i] = change(l[i])
	l.sort()
	s = []
	s.append(l[0])
	s.append(l[1])
	top = l[1]
	st = l[0]
	res = 0
	for i in range(2, n):
		a = -1
		b = -1
		while len(s) >= 2:
			a = s.pop()
			b = s.pop()
			if beauty(a, b) >= beauty(a, l[i]):
				res += pow(beauty(a, b), 2)
				a = -1
				b = -1
			else:
				break
		if a != -1 and b != -1:
			s.append(b)
			s.append(a)
		s.append(l[i])
	while len(s) >= 2:
		a = s.pop()
		b = s.pop()
		res += pow(beauty(a, b), 2)
	print(res)


t = int(input())
for qwe in range(t):
	l = []
	s1 = int(input())
	for i in range(s1):
		s = input()
		for j in range(1, len(s) + 1):
			l.append([j, s[0:j] + s[len(s) - j:], i])
	l.sort(reverse=True)
	a = 0
	c = 1
	if len(l) == 1:
		print(0)
	else:
		d = {}
		ans = 0
		while a <= c < len(l):
			if l[a][1] == l[c][1]:
				ans += l[a][0] ** 2
				d[l[a][2]] = 1
				d[l[c][2]] = 1
			else:
				a += 1
				c += 1
			while a < len(l):
				if l[a][2] not in d:
					break
				else:
					a += 1
			while c < len(l):
				if l[c][2] not in d and a != c:
					break
				else:
					c += 1
		print(ans)


def ispalin(s):
	a = 0
	b = len(s) - 1
	while a < b:
		if s[a] != s[b]:
			return False
		a += 1
		b -= 1
	return True

def f(s1, s2):
	a = len(s1)
	b = len(s2)
	w = count = 0
	while w < min(a, b):
		if s1[w] == s2[w]:
			count += 1
			w += 1
		else:
			break
	return count ** 2

def f1(l1, l2):
	s1 = l1[0]
	s2 = l2[0]
	a = len(s1)
	b = len(s2)
	w = count = 0
	v = 0
	while w < min(a, b):
		if s1[w] == s2[w]:
			count += 1
			w += 1
		else:
			v = 1
			break
	if count % 2 == 1:
		if v == 0 and w == min(a, b):
			p1 = p2 = 0
			s1 = l1[1]
			s2 = l2[1]
			for i in range(min(a, b)):
				if s1[i] == s2[i]:
					p1 += 1
				else:
					break
			if a < b:
				for i in range(min(a, b) - 1, -1, -1):
					if s1[i] == s2[i + b - a]:
						p2 += 1
					else:
						break
			else:
				for i in range(min(a, b) - 1, -1, -1):
					if s1[i + a - b] == s2[i]:
						p2 += 1
					else:
						break
			return min(p1, p2) ** 2
		return ((count - 1) // 2) ** 2
	else:
		return (count // 2) ** 2

def g(s):
	p = len(s)
	if p == 1:
		return s
	w = p // 2
	s1 = ''
	for i in range(w):
		s1 += s[i] + s[p - 1 - i]
	if p % 2 == 1:
		s1 += s[w]
	return s1
for i in range(int(input())):
	x = True
	n = int(input())
	arr1 = []
	for i in range(n):
		arr1.append([input()])
	if not ispalin(arr1[-1][0]):
		x = False
	if x == False:
		for i in range(n):
			arr1[i] = [g(arr1[i][0])] + arr1[i]
		arr1.sort()
		arr = []
		ans = 0
		for i in range(n):
			if arr == []:
				arr.append(arr1[i])
			elif arr[-1][0] == arr1[i][0]:
				ans += len(arr[-1][0]) ** 2
				arr.pop()
			else:
				arr.append(arr1[i])
		l = []
		n = len(arr)
		if n > 1:
			for i in range(n - 1):
				l.append([f1(arr[i], arr[i + 1]), i])
			l1 = []
			for i in l:
				l1.append(i[:])
			l1.sort()
			temp = [0 for i in range(n)]
			neigh = []
			for i in range(n):
				neigh.append([i - 1, i + 1])
			neigh[0][0] = None
			neigh[-1][-1] = None
			index = [0 for i in range(n - 1)]
			for i in range(n - 1):
				index[l1[i][1]] = i
			index.append(n - 1)
			for i in range(n - 2, -1, -1):
				if temp[i] == 1:
					continue
				else:
					ans += l1[i][0]
					p = l1[i][1]
					p1 = neigh[p][1]
					c = index[p1]
					temp[i] = 1
					temp[c] = 1
					q1 = neigh[p][0]
					q2 = neigh[p1][1]
					if q1 == None and q2 == None:
						break
					elif q1 == None:
						neigh[q2][0] = None
						continue
					elif q2 == None:
						neigh[q1][1] = None
						temp[index[q1]] = 1
					else:
						neigh[q1][1] = q2
						neigh[q2][0] = q1
						j1 = index[q1]
						j2 = index[p1]
						if j1 > j2:
							temp[j1] = 1
							temp[j2] = 0
							l1[j2][1] = q1
							index[q1] = j2
		print(ans)
	else:
		arr = []
		for i in arr1:
			arr.append(i[0])
		arr.sort()
		ans = 0
		l = []
		for i in range(n - 1):
			l.append([f(arr[i], arr[i + 1]), i])
		l1 = []
		for i in l:
			l1.append(i[:])
		l1.sort()
		temp = [0 for i in range(n)]
		neigh = []
		for i in range(n):
			neigh.append([i - 1, i + 1])
		neigh[0][0] = None
		neigh[-1][-1] = None
		index = [0 for i in range(n - 1)]
		for i in range(n - 1):
			index[l1[i][1]] = i
		index.append(n - 1)
		ans = 0
		for i in range(n - 2, -1, -1):
			if temp[i] == 1:
				continue
			else:
				ans += l1[i][0]
				p = l1[i][1]
				p1 = neigh[p][1]
				c = index[p1]
				temp[i] = 1
				temp[c] = 1
				q1 = neigh[p][0]
				q2 = neigh[p1][1]
				if q1 == None and q2 == None:
					break
				elif q1 == None:
					neigh[q2][0] = None
					continue
				elif q2 == None:
					neigh[q1][1] = None
					temp[index[q1]] = 1
				else:
					neigh[q1][1] = q2
					neigh[q2][0] = q1
					j1 = index[q1]
					j2 = index[p1]
					if j1 > j2:
						temp[j1] = 1
						temp[j2] = 0
						l1[j2][1] = q1
						index[q1] = j2
		print(ans)


def findBeauty(s1, s2):
	n = min(len(s1), len(s2))
	count = 0
	for i in range(n):
		if s1[i] != s2[i]:
			break
		else:
			count += 1
	b = count
	s1 = s1[::-1]
	s2 = s2[::-1]
	count = 0
	for i in range(n):
		if s1[i] != s2[i] or i > b:
			break
		else:
			count += 1
	b = min(b, count)
	return b * b

def calBeauty(L):
	N = len(L)
	ans = []
	for i in range(N - 1):
		for j in range(i + 1, N):
			left = findBeauty(L[i], L[j])
			if left != 0:
				ans.append([left, i, j])
	ans.sort(reverse=True)
	sum1 = 0
	p = len(ans)
	i = 0
	ans.append([-99, -99, -99])
	while True:
		if ans[i][0] == -99:
			break
		sum1 += ans[i][0]
		j = i + 1
		while True:
			if ans[j][0] == -99:
				break
			if ans[j][1] == ans[i][1] or ans[j][1] == ans[i][2] or ans[j][2] == ans[i][2] or (ans[j][2] == ans[i][1]):
				ans.remove(ans[j])
				j -= 1
			j += 1
		i += 1
	return sum1
for _ in range(int(input())):
	N = int(input())
	L = []
	for i in range(N):
		L.append(input())
	L.sort()
	W = []
	same = []
	for i in range(1, N):
		if L[i] != L[i - 1]:
			W.append(L[i - 1])
			L[i - 1] = ''
		else:
			same.append(L[i])
			L[i - 1] = ''
			L[i] = ''
			i += 1
	W.append(L[-1])
	while '' in W:
		W.remove('')
	beauty = 0
	for x in same:
		r = len(x)
		beauty += r * r
	L = W
	S = []
	k = 0
	N = len(L)
	for i in range(1, N):
		if L[i][0] != L[i - 1][0]:
			S.append(L[k:i])
			k = i
	S.append(L[k:])
	Y = []
	for s in S:
		r = [x[::-1] for x in s]
		k = 0
		r.sort()
		for i in range(len(r)):
			if r[i][0] != r[i - 1][0]:
				Y.append(r[k:i])
				k = i
		Y.append(r[k:])
	for i in range(len(Y)):
		beauty += calBeauty(Y[i])
	print(beauty)


def score(s1, s2):
	count = 0
	for i in range(min(len(s1), len(s2))):
		if s1[i] == s2[i] and s1[-(i + 1)] == s2[-(i + 1)]:
			count += 1
		else:
			break
	return count
for _ in range(int(input())):
	n = int(input())
	words = []
	leng = []
	for i in range(n):
		words.append(input())
		leng.append(len(words[i]))
	d = {}
	maxlen = max(leng)
	for i in range(len(words)):
		words[i] = words[i] + '^' * (maxlen - len(words[i]))
	g = {}
	level = 0
	for i in range(len(words)):
		g[words[i], level] = 0
	for i in range(maxlen):
		group = 1
		for j in range(len(words)):
			i1 = i
			if d.get((words[j][i], words[j][leng[j] - i - 1], i1, g[words[j], level])) == None:
				d[words[j][i], words[j][leng[j] - i - 1], i1, g[words[j], level]] = [words[j]]
				g[words[j], level + 1] = group
				group += 1
			else:
				d[words[j][i], words[j][leng[j] - i - 1], i1, g[words[j], level]].append(words[j])
				g[words[j], level + 1] = g[d[words[j][i], words[j][leng[j] - i - 1], i1, g[words[j], level]][0], level + 1]
		level += 1
	l = []
	done = {}
	lis = []
	for lev in range(level, -1, -1):
		dic = {}
		for i in range(n):
			if done.get((words[i], i)) == None:
				if dic.get(g[words[i], lev]) == None:
					dic[g[words[i], lev]] = [(words[i], i)]
				else:
					done[words[i], i] = 1
					lis.append(words[i])
					done[dic[g[words[i], lev]][0]] = 1
					lis.append(dic[g[words[i], lev]][0][0])
					del dic[g[words[i], lev]]
	ans = 0
	for i in range(0, len(lis), 2):
		ans += pow(score(lis[i].strip('^'), lis[i + 1].strip('^')), 2)
	print(ans)


def check(arr1, arr2):
	j = 0
	n1 = len(arr1)
	n2 = len(arr2)
	count = 0
	while j < n1 and j < n2:
		if arr1[j] == arr2[j]:
			count = count + 1
			j = j + 1
		else:
			break
	return count
for _ in range(int(input())):
	sume = 0
	n = int(input())
	a = []
	for i in range(n):
		p = input()
		a.append(p)
	mno = []
	mno = a
	a = []
	a = list(set(mno))
	n = len(a)
	sume2 = 0
	i = 0
	while i < n:
		x = mno.count(a[i])
		sume2 = sume2 + len(a[i]) * len(a[i]) * (x // 2)
		if x % 2 == 0:
			a.pop(i)
			n = n - 1
			continue
		i = i + 1
	p = []
	(rows, cols) = (n, n)
	arr = [[0 for i in range(cols)] for j in range(rows)]
	for i in range(n):
		for j in range(i, n):
			if i == j:
				p.append(arr[i][j])
				continue
			if a[i] == a[j]:
				arr[i][j] = len(a[i]) ** 2
				arr[j][i] = arr[i][j]
				p.append(arr[i][j])
			else:
				arr[i][j] = min(check(a[i], a[j]), check(a[i][::-1], a[j][::-1])) ** 2
				arr[j][i] = arr[i][j]
				p.append(arr[i][j])
	p = set(p)
	p = list(p)
	p = sorted(p)
	p = p[::-1]
	I = []
	J = []
	for num in p:
		for i in range(n):
			if i not in I:
				if arr[i].count(num) > 0:
					for j in range(n):
						if arr[i][j] == num:
							if j not in J:
								sume = sume + num
								I.append(i)
								J.append(j)
								break
	print(sume2 + sume // 2)


from collections import deque

def prefixal_len(a, b):
	count = 0
	for (a1, b1) in zip(a, b):
		if a1 != b1:
			return count
		count += 1
	else:
		return count

def calc_common_prefixal(w, m, n):
	w.sort()
	res = 0
	x = []
	d = deque()
	for c in w:
		if d:
			p = d.pop()
			common_len = prefixal_len(p[1], c)
			if common_len >= n:
				res += n ** 2
			elif common_len >= m:
				if p[0] > common_len:
					res += p[0] ** 2
					d.pop()
					while d:
						q = d.pop()
						if q[0] > common_len:
							res += q[0] ** 2
							q.pop()
						else:
							d.append((q[0], c))
							break
				else:
					d.append(p)
					d.append((common_len, c))
			else:
				if p[0] == 0:
					x.append(p[1])
				else:
					res += p[0] ** 2
					d.pop()
				while d:
					q = d.pop()
					if q[0] == 0:
						x.append(q[1])
					else:
						res += q[0] ** 2
						d.pop()
				d.append((0, c))
		else:
			d.append((0, c))
	else:
		while d:
			q = d.pop()
			if q[0] > 0:
				res += q[0] ** 2
				d.pop()
			else:
				x.append(q[1])
	return (res, x)

def solve(a):
	a.sort()
	res = 0
	d = deque()
	for c in a:
		if d:
			p = d.pop()
			common_len = prefixal_len(p[1], c)
			if common_len >= 1:
				if p[0] > common_len:
					q = d.pop()
					(r, x) = calc_common_prefixal(p[2], q[0] + 1, p[0])
					res += r
					while q[0] > common_len:
						q2 = d.pop()
						(r, x) = calc_common_prefixal(x + q[2], q2[0] + 1, q[0])
						res += r
						q = q2
					if q[0] == common_len:
						d.append((common_len, c, x + q[2] + [c[::-1]]))
					else:
						d.append(q)
						d.append((common_len, c, x + [c[::-1]]))
				elif p[0] == common_len:
					d.append((common_len, c, p[2] + [c[::-1]]))
				else:
					d.append((p[0], p[1], p[2][:-1]))
					d.append((common_len, c, [p[2][-1], c[::-1]]))
			else:
				if p[0] > 0:
					q = d.pop()
					(r, x) = calc_common_prefixal(p[2], q[0] + 1, p[0])
					res += r
					while q[0] > 0:
						q2 = d.pop()
						(r, x) = calc_common_prefixal(x + q[2], q2[0] + 1, q[0])
						res += r
						q = q2
				d.append((0, c, [c[::-1]]))
		else:
			d.append((0, c, [c[::-1]]))
	else:
		x = []
		if d:
			q = d.pop()
			while q[0] > 0:
				q2 = d.pop()
				(r, x) = calc_common_prefixal(x + q[2], q2[0] + 1, q[0])
				res += r
				q = q2
	return res

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		w = [input() for i in range(N)]
		ans = solve(w)
		print(ans)
main()


from math import factorial as fac
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def read_int():
	return int(f.readline())

def read_int_array():
	return [int(x) for x in f.readline().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def read_string():
	return list(f.readline())
NUMBER = 10 ** 9 + 7

def factorial(n):
	M = 1000000007
	f = 1
	for i in range(1, n + 1):
		f = f * i % M
	return f

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
from collections import defaultdict
import string
LETTERS = list(string.ascii_lowercase)

def transform_string(s):
	n = len(s)
	res = ''
	for i in range(n):
		res += s[i] + s[n - 1 - i]
	return res

def diff_s(s, t):
	i = 0
	while i < min(len(s), len(t)) and s[i] == t[i]:
		i += 1
	return i // 2

def solution(A, N):
	A = [transform_string(x) for x in A]
	A.sort()
	n = len(A)
	diffs = []
	total_sum = 0
	for i in range(n - 1):
		diff = diff_s(A[i], A[i + 1])
		while True:
			if len(diffs) == 0 or diff > diffs[-1]:
				diffs.append(diff)
				break
			total_sum += diffs[-1] ** 2
			if len(diffs) == 1 or diff == diffs[-1]:
				diffs.pop()
				break
			if diff >= diffs[-2]:
				diffs.pop()
				break
			diffs.pop()
			diffs.pop()
	for i in range(len(diffs) - 1, -1, -2):
		total_sum += diffs[i] ** 2
	return total_sum

def main():
	T = read_int()
	for i in range(T):
		N = read_int()
		A = []
		for i in range(N):
			A.append(f.readline().strip())
		print(solution(A, N))
import random

def test():
	A = [[random.choice(LETTERS) for i in range(6)] for i in range(8)]
	print([random.choice(LETTERS) for i in range(5)])
main()


def modstr(a):
	tmp = ''
	l = len(a)
	for i in range(l):
		tmp = tmp + a[i] + a[l - 1 - i]
	return tmp

def func(b, a):
	i = 0
	while i < min(len(a), len(b)) and a[i] == b[i]:
		i += 1
	return (i // 2) ** 2
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		a = input()
		l.append(modstr(a))
	l.sort()
	ans = 0
	prev = -1
	stack = []
	stack.append(l[0])
	i = 1
	tmp = 0
	while i < n:
		while tmp >= prev and i < n:
			k = 0
			stack.append(l[i])
			i += 1
			prev = tmp
			tmp = func(stack[-1], stack[-2])
		while tmp < prev:
			ans += prev
			if prev != 0:
				t1 = stack[-1]
				stack.pop()
				stack.pop()
				stack.pop()
				stack.append(t1)
				if len(stack) > 2:
					tmp = func(stack[-1], stack[-2])
					prev = func(stack[-2], stack[-3])
				elif len(stack) == 2:
					prev = 0
					tmp = func(stack[-1], stack[-2])
				else:
					prev = -1
					tmp = 0
	while len(stack) > 1:
		tmp = func(stack[-1], stack[-2])
		ans += tmp
		stack.pop()
		stack.pop()
	print(ans)


def check(s1, s2):
	if s1 == s2:
		y = len(s1)
		return y
	n = min(len(s1), len(s2))
	c1 = 0
	for i in range(n):
		if s1[i] == s2[i]:
			c1 += 1
		else:
			break
	c2 = 0
	s1 = s1[::-1]
	s2 = s2[::-1]
	for i in range(n):
		if s1[i] == s2[i] or c1 < c2:
			c2 += 1
		else:
			break
	b = min(c1, c2)
	return b
T = int(input())
for _ in range(T):
	N = int(input())
	w = []
	for _ in range(N):
		w.append(input())
	w.sort()
	i = 0
	same = []
	while i < N - 1:
		if w[i] == w[i + 1]:
			same.append(len(w[i]))
			w[i] = ''
			w[i + 1] = ''
			i = i + 2
		else:
			i += 1
	while '' in w:
		w.remove('')
	wlen = len(w)
	i = 0
	while i < wlen - 2:
		if w[i - 1] == '' and w[i][0] != w[i + 1][0]:
			w[i] = ''
		elif w[i][0] != w[i + 1][0]:
			if w[i + 1][0] != w[i + 2][0]:
				w[i + 1] = ''
				i += 1
		i += 1
	while '' in w:
		w.remove('')
	wlen = len(w)
	z = []
	for i in range(wlen):
		for j in range(i + 1, wlen):
			left = check(w[i], w[j])
			if left != 0:
				z.append([left, i, j])
	z.sort(reverse=True)
	sum1 = 0
	p = len(z)
	i = 0
	z.append([-99, -99, -99])
	while True:
		if z[i][0] == -99:
			break
		sum1 += z[i][0] * z[i][0]
		j = i + 1
		while True:
			if z[j][0] == -99:
				break
			if z[j][1] == z[i][1] or z[j][1] == z[i][2] or z[j][2] == z[i][2] or (z[j][2] == z[i][1]):
				z.remove(z[j])
				j -= 1
			j += 1
		i += 1
	for x in same:
		sum1 += x * x
	print(sum1)


from collections import defaultdict

def best_beauty(words):
	max_len = 0
	trie_table = {}
	num_set = defaultdict(set)
	counts = defaultdict(int)
	for (idx, word) in enumerate(words):
		counts[idx] += 1
		chars = ''
		c_idx = 0
		for c_idx in range(len(word)):
			chars += word[c_idx]
			chars += word[~c_idx]
			ln = len(chars) // 2
			num_set[ln].add(chars)
			if chars in trie_table:
				max_len = max(max_len, ln)
			else:
				trie_table[chars] = set()
			trie_table[chars].add(idx)
	result = 0
	for i in range(max_len, 0, -1):
		for word in num_set[i]:
			indexes = trie_table[word]
			if len(indexes) > 1:
				nums = []
				for index in indexes:
					if counts[index] > 0:
						nums.append(index)
					if len(nums) == 2:
						result += i ** 2
						counts[nums[0]] -= 1
						counts[nums[1]] -= 1
						nums = []
	return result
for _ in range(int(input())):
	words = [input() for _ in range(int(input()))]
	print(best_beauty(words))


import math

class Node:

	def __init__(self, char='', parent=None):
		self.char = char
		self.parent = parent
		self.children = {}
		self.count = 0
		if parent is None:
			self.rht = 0
		else:
			self.rht = parent.rht + 1

	def __repr__(self):
		return self.char

def addToTrie(root, s):
	node = root
	for c in s:
		if c in node.children:
			node = node.children[c]
			node.count += 1
		else:
			childnode = Node(char=c, parent=node)
			childnode.count = 1
			node.children[c] = childnode
			node = childnode

def addTupleToTrie(root, s):
	node = root
	l = len(s)
	l2 = math.ceil(l / 2)
	for i in range(l2):
		i_ = l - i - 1
		if i == i_:
			c = s[i]
		else:
			c = s[i] + s[i_]
		if c in node.children:
			node = node.children[c]
			node.count += 1
		else:
			childnode = Node(char=c, parent=node)
			childnode.count = 1
			node.children[c] = childnode
			node = childnode

def printTrie(root):
	printQ = []
	printQ.append(root)
	printQ.append('\n')
	while printQ:
		node = printQ.pop(0)
		if node == '\n':
			print(node)
			if printQ:
				printQ.append('\n')
		else:
			print(node.char, node.value, node.count, node.rht, end=' ')
			printQ.extend(node.children.values())

def getBFS(root):
	visitQ = []
	visitQ.append(root)
	visitPointer = 0
	while visitPointer < len(visitQ):
		node = visitQ[visitPointer]
		visitQ.extend(node.children.values())
		visitPointer += 1
	return visitQ

def getTrieValueBU1(bottomUp):
	buPointer = 0
	l = len(bottomUp)
	while buPointer < l:
		node = bottomUp[buPointer]
		node.value = 0
		node.carry = node.count
		if node.children:
			for child in node.children.values():
				node.value += child.value
				node.carry += child.carry - child.count
		node.value += node.rht ** 2 * (node.carry // 2)
		node.carry = node.carry % 2
		buPointer += 1

def getTrieValueBU2(bottomUp):
	buPointer = 0
	l = len(bottomUp)
	while buPointer < l:
		node = bottomUp[buPointer]
		node.value = 0
		node.carry = node.count
		if node.children:
			factor = 1
			minus = 0
			for child in node.children.values():
				if len(child.char) == 1:
					partner = child.char + child.char
					if partner in node.children:
						if child.carry and node.children[partner].carry:
							node.value += child.rht ** 2
							child.carry = 0
							node.children[partner].carry = 0
				elif child.char[0] == child.char[1]:
					partner = child.char[0]
					if partner in node.children:
						if child.carry and node.children[partner].carry:
							node.value += child.rht ** 2
							child.carry = 0
							node.children[partner].carry = 0
				node.value += child.value
				node.carry += child.carry - child.count
		else:
			factor = 2
			c = node.char
			minus = 2 - len(c)
		node.value += (factor * node.rht - minus) ** 2 * (node.carry // 2)
		node.carry = node.carry % 2
		buPointer += 1
t = int(input())
for _ in range(t):
	n = int(input())
	algoUse = 1
	root = Node()
	lws = []
	for i in range(n):
		w = input().strip()
		lws.append(w)
	w = lws[n // 2]
	if w != w[::-1]:
		algoUse = 2
	if algoUse == 1:
		for w in lws:
			addToTrie(root, w)
	else:
		for w in lws:
			addTupleToTrie(root, w)
	visitQ = getBFS(root)
	bottomUp = visitQ[::-1]
	if algoUse == 1:
		getTrieValueBU1(bottomUp)
	else:
		getTrieValueBU2(bottomUp)
	print(root.value)


class TrieNode(object):

	def __init__(self, char: str):
		self.char = char
		self.children = []
		self.level = 0
		self.counter = set()

def add(root, word, i):
	node = root
	l = 0
	for char in word:
		l += 1
		found_in_child = False
		for child in node.children:
			if child.char == char:
				child.counter.add(i)
				node = child
				found_in_child = True
				break
		if not found_in_child:
			new_node = TrieNode(char)
			node.children.append(new_node)
			node.children[-1].counter.add(i)
			new_node.level = l
			node = new_node
for i in range(int(input())):
	n = int(input())
	root = TrieNode('*')
	root2 = TrieNode('*')
	st = []
	for j in range(n):
		st.append(input())
		add(root, st[-1], j)
		add(root2, st[-1][::-1], j)
	queue = [root]
	l = []
	l.append([])
	while len(queue) != 0:
		node = queue[0]
		queue.pop(0)
		for i in node.children:
			if len(i.counter) >= 2:
				if i.level + 1 > len(l):
					l.append([])
				l[i.level].append(i.counter)
				queue.append(i)
	lr = []
	lr.append([])
	queue = []
	queue = [root2]
	while len(queue) != 0:
		node = queue[0]
		queue.pop(0)
		for i in node.children:
			if len(i.counter) >= 2:
				if i.level + 1 > len(lr):
					lr.append([])
				lr[i.level].append(i.counter)
				queue.append(i)
	il = min(len(l), len(lr)) - 1
	m = []
	for j in range(len(st)):
		m.append(0)
	score = 0
	tag = 0
	while il > 0:
		for j in l[il]:
			for z in lr[il]:
				t = j & z
				c = 0
				for k in t:
					if m[k] == 0:
						c += 1
						tag = k
						m[k] = 1
				if c % 2 == 0:
					score += c / 2 * il ** 2
				else:
					m[tag] = 0
					score += c // 2 * il ** 2
		il -= 1
	print(int(score))


import os.path
import sys
sys.setrecursionlimit(100000000)

def prefix(a, b):
	return len(os.path.commonprefix([a, b])) // 2

def mingle(x):
	(left, right) = (0, len(x) - 1)
	out = ''
	while right >= 0:
		out += x[left]
		out += x[right]
		left += 1
		right -= 1
	return out

def optimal(n, paired, i):
	if n >= len(buckets[i]) - 1:
		return (0, [])
	if memo[n] != -1:
		return memo[n]
	(a, b) = (buckets[i][n], buckets[i][n + 1])
	pre = prefix(a, b)
	value = pre ** 2
	(a, pa) = optimal(n + 2, [], i)
	a += value
	(b, pb) = optimal(n + 1, [], i)
	if a > b:
		ans = a
		paired += [n, n + 1] + pa
	else:
		ans = b
		paired += pb
	memo[n] = (ans, paired)
	return (ans, paired)

def beauties(l):
	return [prefix(l[i], l[i + 1]) for i in range(len(l) - 1)]
original = {}
ans = []
for t in range(int(input())):
	buckets = {}
	n = int(input())
	for i in range(n):
		temp = input()
		out = mingle(temp)
		iden = temp[0] + temp[-1]
		if iden in buckets:
			buckets[iden].append(out)
		else:
			buckets[iden] = [out]
		original[out] = temp
	value = 0
	for i in buckets:
		lenn = len(buckets[i])
		if lenn == 1:
			continue
		buckets[i].sort()
		if lenn > 1000:
			while True:
				memo = [-1 for i in range(n)]
				choice = optimal(0, [], i)
				if choice[0] == 0:
					break
				value += choice[0]
				for (j, idx) in enumerate(choice[1]):
					del buckets[i][idx - j]
		else:
			l = beauties(buckets[i])
			possible = []
			for i in range(len(l)):
				m = float('inf')
				for j in range(i, len(l)):
					if l[j] < m:
						m = l[j]
					if m == 0:
						break
					possible.append((m ** 2, i, j + 1))
			possible.sort(reverse=True)
			used = set()
			for (m, i, j) in possible:
				if i in used or j in used:
					continue
				used.add(i)
				used.add(j)
				value += m
	ans.append(str(value))
print('\n'.join(ans))


def maxxx(s, w):
	maxx = -1
	bb = 0
	rhyme = -1
	for i in w:
		if i == s:
			continue
		count = 0
		while count < len(i) and count < len(s) and (i[count] == s[count]) and (i[len(i) - count - 1] == s[len(s) - count - 1]):
			count += 1
		bb = count ** 2
		if bb > maxx and bb > 0:
			maxx = bb
			rhyme = i
	return (rhyme, maxx)
try:
	t = int(input())
	for r in range(t):
		n = int(input())
		words = []
		done = {}
		to = 0
		for i in range(n):
			s = input()
			if s in done:
				to += len(s) ** 2
				del done[s]
			else:
				done[s] = 1
				if s not in words:
					words.append(s)
		w = []
		for i in words:
			if i in done:
				w.append(i)
		w.sort()
		while len(w) > 1:
			a = []
			i = w[0]
			tt = i
			while tt not in a:
				a.append(tt)
				m = maxxx(tt, w)
				if m[0] == -1:
					w.pop(w.index(tt))
					tt = w[0]
					break
				k = maxxx(m[0], w)
				if k[0] == tt:
					to += k[1]
					w.pop(w.index(tt))
					w.pop(w.index(m[0]))
					break
				tt = m[0]
		print(to)
except:
	pass


def findmax(x, w):
	max = -1
	beauty = 0
	verse = -1
	for i in w:
		if i == x:
			continue
		c = 0
		while c < len(i) and c < len(x) and (i[c] == x[c]) and (i[len(i) - c - 1] == x[len(x) - c - 1]):
			c += 1
		beauty = c ** 2
		if beauty > max and beauty > 0:
			max = beauty
			verse = i
	return (verse, max)
for _ in range(int(input())):
	n = int(input())
	Words = []
	d = {}
	maxlen = 0
	total = 0
	for i in range(n):
		x = input()
		if x in d:
			total += len(x) ** 2
			del d[x]
		else:
			d[x] = 1
			if x not in Words:
				Words.append(x)
	W = []
	for i in Words:
		if i in d:
			W.append(i)
	W.sort()
	while len(W) > 1:
		a = []
		i = W[0]
		temp = i
		while temp not in a:
			a.append(temp)
			m = findmax(temp, W)
			if m[0] == -1:
				W.pop(W.index(temp))
				temp = W[0]
				break
			k = findmax(m[0], W)
			if k[0] == temp:
				total += k[1]
				W.pop(W.index(temp))
				W.pop(W.index(m[0]))
				break
			temp = m[0]
	print(total)


T = int(input())
while T:
	N = int(input())
	ls = []
	for i in range(N):
		W = input()
		ls.append(W)
	ls.sort()
	ans = 0
	new_ls = []
	count = 0
	for i in range(N):
		if i == 0:
			count += 1
			if i == N - 1:
				ans += len(ls[i]) ** 2 * (count // 2)
				if count % 2 != 0:
					new_ls.append(ls[i])
		elif ls[i] == ls[i - 1]:
			count += 1
			if i == N - 1:
				ans += len(ls[i]) ** 2 * (count // 2)
				if count % 2 != 0:
					new_ls.append(ls[i])
		else:
			ans += len(ls[i - 1]) ** 2 * (count // 2)
			if count % 2 != 0:
				new_ls.append(ls[i - 1])
			count = 1
			if i == N - 1:
				ans += len(ls[i]) ** 2 * (count // 2)
				if count % 2 != 0:
					new_ls.append(ls[i])
	greedy = []
	for i in range(len(new_ls)):
		for j in range(i + 1, len(new_ls)):
			score = 0
			for k in range(min(len(new_ls[i]), len(new_ls[j]))):
				if new_ls[i][k] == new_ls[j][k] and new_ls[i][len(new_ls[i]) - k - 1] == new_ls[j][len(new_ls[j]) - k - 1]:
					score += 1
				else:
					break
			greedy.append([score, new_ls[i], new_ls[j]])
	greedy.sort(reverse=True)
	a = set()
	for i in range(len(greedy)):
		if greedy[i][1] not in a and greedy[i][2] not in a:
			ans += greedy[i][0] ** 2
			a.add(greedy[i][1])
			a.add(greedy[i][2])
	print(ans)
	T -= 1