Insidious Branding

"I know a trick worth two of that"

-- William Shakespeare, Henry IV, Part 1, Act II, Scene 1

A brand designer has proposed a strategy that could be the key to your company's success — and therefore to yours. The idea is to pick a brand name that can be split into a pair of common everyday words in two different ways, then bombard consumers with all four words in short bursts of sensory overload. The consumer's mind is jarred, and the brand eases its way into long-term memory.

Your task is to write a program that searches a dictionary for combinations of four words (not necessarily distinct) $A$, $B$, $C$, and $D$ that satisfy

$A + B = C + D$

where $+$ denotes concatenation, $=$ denotes an exact string match, the length of $A$ is strictly less than the length of $C$, and all four words are non-empty.

The input contains several test cases; each test case uses its own dictionary. A test case begins with a line containing an integer $W$ ($1 \le W < 100{,}000$), the number of words in the dictionary. Each of the next $W$ lines contains one word. The words appear in no particular order and are all distinct within a test case. Each word is a string of $L$ lowercase letters and contains no spaces, where $1 < L < 30$. The input ends with a line containing a single $0$.

For each test case, output on its own line a single integer: the number of equations $A + B = C + D$ that can be formed.