Hạo đang học tiếng Anh. Cho đến nay, Hạo đã biết \(N\) từ vựng, và anh ấy muốn viết một bài thơ. Chúng ta hãy coi một cặp từ tiếng Anh là một khổ thơ. Một bài thơ là một tập hợp các khổ thơ. Vần tiền tố của một khổ thơ là tiền tố chung dài nhất của các từ trong đó. Tương tự, vần hậu tố của một khổ thơ là hậu tố chung dài nhất của các từ trong đó. Một khổ thơ có vần tiền tố và vần hậu tố có độ dài lần lượt là \(l_{pref}\) và \(l_{suf}\) sẽ có vẻ đẹp tương ứng là là \(min(l_{pref}, l_{suf})^2\)

Ví dụ, một khổ thơ được hình thành bởi các từ "abcdefghijkl" và "abcxyzhijkl" có một vần tiền tố "abc" (với độ dài \(3\)), vần hậu tố "hijkl" (với độ dài \(5\)) và vẻ đẹp là \(min(3, 5)^2 = 3^2 = 9\).

Vẻ đẹp của một bài thơ là tổng hợp vẻ đẹp của tất cả các khổ thơ của nó. Ví dụ: vẻ đẹp của bài thơ (("abcdefghijkl", "abcxyzhijkl"), ("world", "word"), ("hao", "code")) là \(9 + 1 + 0 = 10\).

Bạn được cung cấp \(N\) từ \(W_1, W_2, …, W_N\) (chúng không nhất thiết phải khác nhau). Hãy giúp Hạo viết những bài thơ hay nhất (vẻ đẹp lớn nhất). Không cần thiết phải sử dụng tất cả các từ, nhưng mỗi từ chỉ có thể được sử dụng nhiều nhất một lần trong toàn bài thơ (tức là, mỗi phần tử trong dãy \(W\) chỉ có thể được sử dụng một lần, nhưng nếu một số từ xuất hiện \(k\) lần trong \(W\), chúng ta có thể sử dụng nó tới \(k\) lần).

Dữ liệu vào

• Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(T\) – số test. \(T\) test được miêu tả như sau:
• Dòng đầu tiên của mỗi test chứa một số nguyên \(N\).
• \(N\) dòng tiếp theo, với mỗi \(i\) \((1 \le i \le N)\), dòng thứ \(i\) chứa một xâu \(W_i\).

Dữ liệu ra

• Với mỗi test, in ra một dòng chứa một số nguyên – vẻ đẹp lớn nhất của bài thơ Hạo sáng tác

Ràng buộc

• \(1 \le T \le 10^5\)
• \(1 \le N \le 10^5\)
• \(1 \le |W_i| \le 10^5\) với mọi \(i\)
• Tất cả các từ chỉ chứa chữ cái thường tiếng Anh.
• Tổng của \(|W1_| + |W_2| + … + |W_N|\) trong tất cả các test không vượt quá \(10^5\)

Subtasks

• Subtask #1 (50 điểm): Tất cả các từ đều là palindrome (đọc xuôi ngược giống nhau).
• Subtask #2 (50 điểm): Các ràng buộc gốc.

Input 1

3
6
abcdefghijkl
chef
world
code
abcxyzhijkl
word
4
problem
poem
problem
problem
3
contest
coolest
unused

Output 1

10
50
4