시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 7 2 2 40.000%

문제

대부분의 운영 체제는 컴퓨터 하드 드라이브에 있는 파일의 내용에 따라서 인덱싱을 한다. 각 파일의 내용은 알파벳 소문자로 이루어져 있는 비어있지 않은 문자열이다.

검색을 하기 위해서는 검색어가 필요하다. 검색어도 알파벳 소문자로 이루어진 비어있지 않은 문자열이다.

검색 결과는 검색어를 부분 문자열로 포함하고 있는 모든 파일이다.

문자열 s가 문자열 t의 부분 문자열이 되려면, t에서 s가 연속되게 나타나야 한다. 예를 들어, "foofoo", "cafoo", "foota", "foo"는 모두 "foo"를 부분 문자열로 포함하고 있다. 하지만, "foa", "fofo", "fioo", "oofo"는 포함하지 않는다.

상근이는 자신의 하드 드라이브에 있는 모든 파일의 내용을 알고 있다. 상근이는 어떠한 파일의 부분 집합이 검색 가능한지 알아내려고 한다.

파일의 부분 집합이 검색 가능하려면, 그러한 파일의 부분 집합을 결과로 보여주는 검색어가 있는 경우이다. 

상근이의 하드 드라이브에 있는 모든 파일의 내용이 주어졌을 때, 검색 가능한 파일의 부분 집합의 개수를 구하는 프로그램을 작성하시오. 부분 집합은 비어있지 않다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

테스트 케이스의 첫째 줄에는 하드 드라이브에 있는 파일의 개수 F가 주어진다. (1 ≤ F ≤ 60). 다음 F개 줄에는 각 파일의 내용이 주어진다. 파일의 내용은 많아야 104개의 문자로 이루어져 있으며, 알파벳 소문자로만 이루어져 있다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 검색 가능한 파일의 부분 집합의 개수를 출력한다.

예제 입력 1

6
form
formal
malformed
for
man
remake
3
cool
cool
old
0

예제 출력 1

11
3
W3sicHJvYmxlbV9pZCI6IjU2ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWM3N2MgXHVhYzgwXHVjMGM5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzMDBcdWJkODBcdWJkODRcdWM3NTggXHVjNmI0XHVjNjAxIFx1Y2NiNFx1YzgxY1x1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHVkNTU4XHViNGRjIFx1YjRkY1x1Yjc3Y1x1Yzc3NFx1YmUwY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YjBiNFx1YzZhOVx1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzc4XHViMzcxXHVjMmYxXHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjODBcdWMwYzlcdWM3NDQgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBcdWFjODBcdWMwYzlcdWM1YjRcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWFjODBcdWMwYzlcdWM1YjRcdWIzYzQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4MFx1YzBjOSBcdWFjYjBcdWFjZmNcdWIyOTQgXHVhYzgwXHVjMGM5XHVjNWI0XHViOTdjIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVkMzBjXHVjNzdjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjQgc1x1YWMwMCBcdWJiMzhcdWM3OTBcdWM1ZjQgdFx1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YjQxOFx1YjgyNFx1YmE3NCwgdFx1YzVkMFx1YzExYyBzXHVhYzAwIFx1YzVmMFx1YzE4ZFx1YjQxOFx1YWM4YyBcdWIwOThcdWQwYzBcdWIwOThcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAmcXVvdDtmb29mb28mcXVvdDssICZxdW90O2NhZm9vJnF1b3Q7LCAmcXVvdDtmb290YSZxdW90OywgJnF1b3Q7Zm9vJnF1b3Q7XHViMjk0IFx1YmFhOFx1YjQ1MCAmcXVvdDtmb28mcXVvdDtcdWI5N2MgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsICZxdW90O2ZvYSZxdW90OywgJnF1b3Q7Zm9mbyZxdW90OywgJnF1b3Q7ZmlvbyZxdW90OywgJnF1b3Q7b29mbyZxdW90O1x1YjI5NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1ZDU1OFx1YjRkYyBcdWI0ZGNcdWI3N2NcdWM3NzRcdWJlMGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQzMGNcdWM3N2NcdWM3NTggXHViMGI0XHVjNmE5XHVjNzQ0IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1YjRcdWI1YTBcdWQ1NWMgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHVhYzgwXHVjMGM5IFx1YWMwMFx1YjJhNVx1ZDU1Y1x1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzMGNcdWM3N2NcdWM3NTggXHViZDgwXHViZDg0IFx1YzlkMVx1ZDU2OVx1Yzc3NCBcdWFjODBcdWMwYzkgXHVhYzAwXHViMmE1XHVkNTU4XHViODI0XHViYTc0LCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVhY2IwXHVhY2ZjXHViODVjIFx1YmNmNFx1YzVlY1x1YzhmY1x1YjI5NCBcdWFjODBcdWMwYzlcdWM1YjRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1ZDU1OFx1YjRkYyBcdWI0ZGNcdWI3N2NcdWM3NzRcdWJlMGNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQzMGNcdWM3N2NcdWM3NTggXHViMGI0XHVjNmE5XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWM4MFx1YzBjOSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWJkODBcdWJkODQgXHVjOWQxXHVkNTY5XHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NThcdWI0ZGMgXHViNGRjXHViNzdjXHVjNzc0XHViZTBjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzMGNcdWM3N2NcdWM3NTggXHVhYzFjXHVjMjE4IEZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEYgJmxlOyA2MCkuIFx1YjJlNFx1Yzc0YyBGXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YjBiNFx1YzZhOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NDAgXHViOWNlXHVjNTQ0XHVjNTdjIDEwPHN1cD40PFwvc3VwPlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YWM4MFx1YzBjOSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkMzBjXHVjNzdjXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1Njg1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlsZSBSZXRyaWV2YWwiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBvcGVyYXRpbmcgc3lzdGVtIG9mIHlvdXIgY29tcHV0ZXIgaW5kZXhlcyB0aGUgZmlsZXMgb24geW91ciBoYXJkIGRpc2sgYmFzZWQgb24gdGhlaXIgY29udGVudHMsIGFuZCBwcm92aWRlcyB0ZXh0dWFsIHNlYXJjaCBvdmVyIHRoZW0uIFRoZSBjb250ZW50IG9mIGVhY2ggZmlsZSBpcyBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgbG93ZXJjYXNlIGxldHRlcnMuIFRvIGRvIGEgc2VhcmNoLCB5b3Ugc3BlY2lmeSBhIGtleSwgd2hpY2ggaXMgYWxzbyBhIG5vbi1lbXB0eSBzdHJpbmcgb2YgbG93ZXJjYXNlIGxldHRlcnMuIFRoZSByZXN1bHQgaXMgYSBsaXN0IG9mIGFsbCB0aGUgZmlsZXMgdGhhdCBjb250YWluIHRoZSBrZXkgYXMgYSBzdWJzdHJpbmcuIEEgc3RyaW5nIHMgaXMgYSBzdWJzdHJpbmcgb2YgYSBzdHJpbmcgdCBpZiB0IGNvbnRhaW5zIGFsbCBjaGFyYWN0ZXJzIG9mIHMgYXMgYSBjb250aWd1b3VzIHNlcXVlbmNlLiBGb3IgaW5zdGFuY2UsICZsZHF1bztmb29mb28mcmRxdW87LCAmbGRxdW87Y2Fmb28mcmRxdW87LCAmbGRxdW87Zm9vdGEmcmRxdW87IGFuZCAmbGRxdW87Zm9vJnJkcXVvOyBhbGwgY29udGFpbiAmbGRxdW87Zm9vJnJkcXVvOyBhcyBhIHN1YnN0cmluZywgd2hpbGUgJmxkcXVvO2ZvYSZyZHF1bzssICZsZHF1bztmb2ZvJnJkcXVvOywgJmxkcXVvO2Zpb28mcmRxdW87IGFuZCAmbGRxdW87b29mbyZyZHF1bzsgZG8gbm90LjxcL3A+XHJcblxyXG48cD5Zb3Uga25vdyB0aGUgY29udGVudCBvZiBlYWNoIGZpbGUgb24geW91ciBoYXJkIGRpc2ssIGFuZCB3b25kZXIgd2hldGhlciBlYWNoIHN1YnNldCBvZiB0aGUgZmlsZXMgaXMgc2VhcmNoYWJsZS4gQSBzdWJzZXQgb2YgdGhlIGZpbGVzIGlzIHNlYXJjaGFibGUgaWYgdGhlcmUgZXhpc3RzIGF0IGxlYXN0IG9uZSBrZXkgdGhhdCBwcm9kdWNlcyBleGFjdGx5IHRoZSBsaXN0IG9mIHRob3NlIGZpbGVzIGFzIGEgcmVzdWx0LiBHaXZlbiB0aGUgY29udGVudHMgb2YgdGhlIGZpbGVzIG9uIHlvdXIgaGFyZCBkaXNrLCB5b3UgYXJlIGFza2VkIHRvIGNvbXB1dGUgdGhlIG51bWJlciBvZiBub24tZW1wdHkgc2VhcmNoYWJsZSBzdWJzZXRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2UgaXMgZGVzY3JpYmVkIHVzaW5nIHNldmVyYWwgbGluZXMuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgRiByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBmaWxlcyBvbiB5b3VyIGhhcmQgZGlzayAoMSAmbGU7IEYgJmxlOyA2MCkuIEVhY2ggb2YgdGhlIG5leHQgRiBsaW5lcyBpbmRpY2F0ZXMgdGhlIGNvbnRlbnQgb2Ygb25lIG9mIHRoZSBmaWxlcy4gVGhlIGNvbnRlbnQgb2YgYSBmaWxlIGlzIGEgbm9uLWVtcHR5IHN0cmluZyBvZiBhdCBtb3N0IDEwNCBjaGFyYWN0ZXJzOyBlYWNoIGNoYXJhY3RlciBpcyBvbmUgb2YgdGhlIDI2IHN0YW5kYXJkIGxvd2VyY2FzZSBsZXR0ZXJzIChmcm9tICZsc3F1bzthJnJzcXVvOyB0byAmbHNxdW87eiZyc3F1bzspLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCB0ZXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgb25lIHplcm88XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IGEgbGluZSB3aXRoIGFuIGludGVnZXIgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2Ygbm9uLWVtcHR5IHNlYXJjaGFibGUgc3Vic2V0cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=