Yong Zheng's Death

Time Limit: 20000/10000 MS (Java/Others)

Memory Limit: 512000/512000 K (Java/Others)

Description

Some Chinese emperors ended up with a mysterious death. Many historians like to do researches about this. For example, the 5th Qing dynasty emperor Yong Zheng's death is often argued among historians. Someone say that he was killed by the top assassin Lu Siniang whose family were almost wiped out by Yong Zheng. Someone say that Yong Zheng was poisoned to death because he liked to eat all kinds of Chinese medicines which were said to have the functions of prolonging human lives. Recently, a new document was discovered in Gu Gong(the Forbidden City). It is a secret document written by Yong Zheng's most trusted eunuch. It reads on the cover: "This document tells how Yong Zheng died. But I can't write this in plain text. Whether people will understand this is depend on Gods." Historians finally found out that there are totally n strings in the document making a set S = { s1,s2,... sn}. You can make some death ciphers from the set. A string is called a DEATH CIPHER if and only if it can be divide into two substrings u and v, and u and v are both a prefix of a string from S (Note that u and v can't be empty strings, and u and v can be prefixes of a same string or two different strings).

When all DEATH CIPHERs are put together, a readable article revealing Yong Zheng's death will appear.

Please help historians to figure out the number of different death ciphers.

Input

The input consists of no more than 20 test cases.

For each case, the first line contains an integer n(1 <= n <= 10000), indicating the number of strings in S.

The following n lines contain n strings, indicating the strings in S. Every string only consists of lower case letters and its length is between 1 and 30(inclusive).

The input ends by n = 0.

Output

For each test case, print a number denoting the number of death ciphers.

Sample Input

2 ab ac 0

Sample Output

9
Hint
For the sample , the death ciphers are {aa, aba, aca, aab, aac, abac, acab, abab, acac}

Hint

liuyiding

Source

2014ACM/ICPC亚洲区广州站-重现赛(感谢华工和北大)

提交代码