Insidious Branding#3048
A brand designer has developed a strategy that you believe will be the key to the success of your company, and therefore, you. The strategy is to use a brand name that can be decomposed in two ways into a pair of commonly used everyday words, and then expose the consumer to the four words repeatedly in short episodes of sensory bombardment. The feeble mind of the consumer will be shaken, and the brand will easily settle into the victim's long-term memory. Your task is to write a program that explores a dictionary for combinations of four words (not necessarily distinct), say , , , and , which satisfy the equation A+B=C+D, where «» denotes concatenation, «» denotes an exact string match, the length of the word is strictly less than the length of the word , and all four strings are not empty.
The input consists of multiple cases. Each case uses one dictionary. A case starts with an integer (1 \leq W < 100000) on a line by itself, indicating the number of words in the dictionary. Each of the following lines contains a single word. The words are in no particular order and are all distinct within a test case. Each word is a string of lowercase Latin letters and contains no spaces, where 1 \leq L \leq 30. The input is terminated by a zero on a line by itself.
The output consists of a single integer on a line by itself, representing the number of equations that can be formed.
Example 1