Задачі
Пошук файлів
Пошук файлів
Операційна система Вашого комп'ютера індексуєт файли, розміщені на жорсткому диску, грунтуючись на їхньому вмісті, а також дозволяє виконувати по ним текстовий пошук. Вміст кожного файлу - непорожній рядок прописних букв. Для виконання пошуку Ви вказуєте ключ, який є непорожнім рядком, що складється з прописних букв. Результатом є список файлів, які містять ключ як підрядок. Рядок \textbf{s} є підрядком \textbf{t}, якщо \textbf{t} містить усі символи \textbf{s} у вигляді неперервної послідовності. Наприклад, "\textbf{foofoo}", "\textbf{cafoo}", "\textbf{foota}" та "\textbf{foo}" усі містять "\textbf{foo}" як підрядок, у той час яак "\textbf{foa}", "\textbf{fofo}", "\textbf{ oo}" та "\textbf{oofo}" ні.
Вам відомий вміст кожного файлу на жорсткому диску. Вас цікавить, чи можна здійснити пошук для довільної підмножини файлів. Пошук для підмножини файлів здійснити можна, якщо існує хоча б один такий ключ, в результаті пошуку за яким буде знайдена у точності наявна підмножина файлів. За заданим вмістом файлів на жорсткому диску Вам потрібно знайти кількість непорожніх підмножин файлів, для яких можливо здійснити пошук.
\InputFile
Кожен тест задається у декількох рядках. Перший рядок містить кількість файлів на жорсткому диску \textbf{f} (\textbf{1} ≤ \textbf{f} ≤ \textbf{60}). Кожен з наступних \textbf{f} рядків задає вміст одного файлу. Вміст файлу являє собою непорожній рядок із не більше ніж \textbf{10^4} символів; кожен символ - одна зі стандартних \textbf{26} прописних букв (від '\textbf{a}' до '\textbf{z}').
За останнім тестом йде рядок з одного нуля.
\OutputFile
Для кожного тесту вивести у окремому рядку кількість непорожніх підмножин файлів, для яких можливо здійснити пошук.
Вхідні дані #1
6 form formal malformed for man remake 3 cool cool old 0
Вихідні дані #1
11 3