교묘한 브랜딩

"나에게는 그보다 두 배는 쓸 만한 수가 있다네"

-- 윌리엄 셰익스피어, 『헨리 4세』 제1부, 2막 1장

한 브랜드 디자이너가 당신 회사의 성공, 나아가 당신 자신의 성공을 좌우할 만한 전략을 제안했다. 핵심은 서로 다른 두 가지 방법으로 흔히 쓰는 일상 단어 두 개로 쪼갤 수 있는 브랜드 이름을 고른 뒤, 짧고 강렬한 감각 자극 속에서 그 네 단어를 소비자에게 반복적으로 노출하는 것이다. 소비자의 정신은 흔들리고, 브랜드는 어느새 장기 기억 속으로 스며든다.

주어진 사전에서, 다음 식을 만족하는 네 단어(서로 다를 필요는 없다) $A$, $B$, $C$, $D$의 조합이 몇 개인지 세는 프로그램을 작성하라.

$A + B = C + D$

여기서 $+$는 문자열을 이어 붙이는 연산(concatenation), $=$는 두 문자열이 정확히 같음을 뜻한다. $A$의 길이는 $C$의 길이보다 반드시 작아야 하며, 네 단어는 모두 비어 있지 않아야 한다.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 자신만의 사전 하나를 사용한다. 각 테스트 케이스는 사전에 들어 있는 단어의 개수 $W$ ($1 \le W < 100{,}000$)가 적힌 한 줄로 시작한다. 이어지는 $W$개의 줄에는 각각 단어가 하나씩 주어진다. 단어들은 특별한 순서 없이 주어지며, 한 테스트 케이스 안에서 모두 서로 다르다. 각 단어는 공백이 없는 소문자 $L$개로 이루어진 문자열이며, $1 < L < 30$이다. 입력의 끝은 $0$ 하나만 있는 줄로 표시된다.

각 테스트 케이스마다, 만들 수 있는 식 $A + B = C + D$의 개수를 한 줄에 정수 하나로 출력한다.