부분 문자열 보내기

당신은 권위 있는 국제 코드 인쇄 대회(ICPC) 파이널 라운드의 참가자다. 시범 라운드 장소에 도착해 보니, 일반 프로그래밍 대회와 달리 어느 팀이든 다른 어느 팀에게나 인쇄용 코드를 보낼 수 있었다.

주최 측은 종이 비용을 추가로 쓰고 싶지 않고, 문제 풀이 힌트가 숨어 있는지 메시지를 검사하고 싶지도 않다. 그래서 다른 팀에게 텍스트를 인쇄용으로 보내려면 다음 조건을 지켜야 한다.

• $S$를 보내는 팀의 이름, $T$를 받는 팀의 이름이라 할 때, 보내는 텍스트는 $S$와 $T$의 공백이 아닌 부분 문자열이어야 한다.
• 한 팀은 같은 메시지를 같은 상대 팀에게 두 번 보낼 수 없다.

문제를 푸는 것도 즐겁지만, 상대 팀에게 메시지를 보내는 일도 재미있다. 대회 동안 서로 다른 팀 사이에서 이런 방식으로 전달될 수 있는 메시지의 최대 개수를 구하라.

어떤 메시지가 여러 순서쌍의 팀 사이에서 전달되면, 그 횟수만큼 답에 센다. 팀이 자기 자신에게 인쇄한 메시지는 세지 않는다.

첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$($1 \leq T \leq 10^5$)가 주어진다.

각 테스트 케이스는 팀의 개수를 나타내는 정수 $n$($1 \leq n \leq 10^5$)으로 시작한다.

이어지는 $n$개의 줄에는 각각 소문자 라틴 알파벳으로만 이루어진 문자열 $S$($1 \leq |S| \leq 10^5$)가 주어진다. 이는 팀의 이름이다. 팀 이름은 중복될 수 있다.

모든 테스트 케이스의 팀 개수 합은 $10^5$를 넘지 않고, 모든 팀 이름 길이의 합은 $5 \cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다, 서로 다른 팀 사이에서 전달될 수 있는 메시지의 최대 개수를 나타내는 정수 하나를 출력한다.

첫 번째 테스트 케이스에서 각 팀은 다른 팀에게 다음 문자열을 보낼 수 있다: a, ab, b, c.

두 번째 테스트 케이스에서 a, d, f, i, m, n, o, re, t, un, um 문자열은 두 가지 방법으로, e, r, s 문자열은 여섯 가지 방법으로, u 문자열은 열두 가지 방법으로 보낼 수 있다.