{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e 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\u0027s 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\u0027s most trusted eunuch. It reads on the cover: \"This document tells how Yong Zheng died. But I can\u0027t 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 \u003d { 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\u0027t be empty strings, and u and v can be prefixes of a same string or two different strings).\u003cbr\u003e\u003cbr\u003e When all DEATH CIPHERs are put together, a readable article revealing Yong Zheng\u0027s death will appear.\u003cbr\u003e\u003cbr\u003e Please help historians to figure out the number of different death ciphers. \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The input consists of no more than 20 test cases.\u003cbr\u003e\u003cbr\u003e For each case, the first line contains an integer n(1 \u0026lt;\u003d n \u0026lt;\u003d 10000), indicating the number of strings in S.\u003cbr\u003e\u003cbr\u003e 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). \u003cbr\u003e\u003cbr\u003e The input ends by n \u003d 0."}},{"title":"Output","value":{"format":"HTML","content":" For each test case, print a number denoting the number of death ciphers."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\nab\r\nac\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"For the sample , the death ciphers are {aa, aba, aca, aab, aac, abac, acab, abab, acac}"}}]}