시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 100 18 17 22.667%

문제

준규는 새로운 언어인 "조말어"를 창조하려고 한다. 먼저, 준규는 조말어의 기초가 되는 단어를 모두 적은 목록을 만들었다. 이 목록에 있는 단어를 "기초 어휘"라고 한다.

이제 기초 어휘를 가지고 새로운 단어를 창조하여 "조말어대사전"을 만들 것이다. "조말어대사전"에 수록될 단어들은 다음의 조건 중 하나를 만족해야 한다.

  • "기초 어휘"이다.
  • 단어를 두 부분으로 나누었을 때, 앞 부분이 기초 어휘의 앞 부분(혹은 전체)이고, 뒷 부분이 기초어휘의 뒷 부분(혹은 전체)이다. (앞 부분과 뒷 부분은 prefix와 suffix로 이해하면 된다)

위의 규칙을 따른 조말어대사전에는 총 몇 개의 단어들이 수록될까?

입력

첫째 줄에는 기초 어휘의 개수 n(1 ≤ n ≤ 10 000)이 주어진다. 그 다음, n개의 줄에는 각 기초 어휘가 주어진다. 기초 어휘는 길이가 1이상 40이하 이며 소문자 알파벳으로 이루어져있다. 

또한 준규는 매우 게을러서 기초 어휘 목록에 중복된 단어가 있는지 검사하지 않는다. 주의하자.

출력

조말어대사전에 수록될 단어의 개수를 출력한다.

예제 입력 1

3
abc
def
abef

예제 출력 1

60
W3sicHJvYmxlbV9pZCI6IjM0OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM4MDRcdWM3NTggXHVkMDZjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1YzViOFx1YzViNFx1Yzc3OCAmcXVvdDtcdWM4NzBcdWI5ZDBcdWM1YjQmcXVvdDtcdWI5N2MgXHVjYzNkXHVjODcwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWM5MDBcdWFkZGNcdWIyOTQgXHVjODcwXHViOWQwXHVjNWI0XHVjNzU4IFx1YWUzMFx1Y2QwOFx1YWMwMCBcdWI0MThcdWIyOTQgXHViMmU4XHVjNWI0XHViOTdjIFx1YmFhOFx1YjQ1MCZuYnNwO1x1YzgwMVx1Yzc0MCBcdWJhYTlcdWI4NWRcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWM3NzQgXHViYWE5XHViODVkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI5N2MmbmJzcDsmcXVvdDtcdWFlMzBcdWNkMDggXHVjNWI0XHVkNzE4JnF1b3Q7XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YWUzMFx1Y2QwOCBcdWM1YjRcdWQ3MThcdWI5N2MmbmJzcDtcdWFjMDBcdWM5YzBcdWFjZTAgXHVjMGM4XHViODVjXHVjNmI0IFx1YjJlOFx1YzViNFx1Yjk3YyZuYnNwO1x1Y2MzZFx1Yzg3MFx1ZDU1OFx1YzVlYyZuYnNwOyZxdW90O1x1Yzg3MFx1YjlkMFx1YzViNFx1YjMwMFx1YzBhY1x1YzgwNCZxdW90O1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVhYzgzXHVjNzc0XHViMmU0LiAmcXVvdDtcdWM4NzBcdWI5ZDBcdWM1YjRcdWIzMDBcdWMwYWNcdWM4MDQmcXVvdDtcdWM1ZDAgXHVjMjE4XHViODVkXHViNDIwIFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjODcwXHVhYzc0Jm5ic3A7XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyZuYnNwO1x1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JnF1b3Q7XHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOCZxdW90O1x1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMmU4XHVjNWI0XHViOTdjIFx1YjQ1MCBcdWJkODBcdWJkODRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjNTVlIFx1YmQ4MFx1YmQ4NFx1Yzc3NCZuYnNwO1x1YWUzMFx1Y2QwOCBcdWM1YjRcdWQ3MThcdWM3NTggXHVjNTVlIFx1YmQ4MFx1YmQ4NChcdWQ2MzlcdWM3NDAgXHVjODA0XHVjY2I0KVx1Yzc3NFx1YWNlMCwgXHViNGI3IFx1YmQ4MFx1YmQ4NFx1Yzc3NCZuYnNwO1x1YWUzMFx1Y2QwOFx1YzViNFx1ZDcxOFx1Yzc1OCBcdWI0YjcgXHViZDgwXHViZDg0KFx1ZDYzOVx1Yzc0MCBcdWM4MDRcdWNjYjQpXHVjNzc0XHViMmU0LiAoXHVjNTVlIFx1YmQ4MFx1YmQ4NFx1YWNmYyBcdWI0YjcgXHViZDgwXHViZDg0XHVjNzQwIHByZWZpeFx1YzY0MCBzdWZmaXhcdWI4NWMgXHVjNzc0XHVkNTc0XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3OCBcdWM4NzBcdWI5ZDBcdWM1YjRcdWIzMDBcdWMwYWNcdWM4MDRcdWM1ZDBcdWIyOTQgXHVjZDFkIFx1YmE4NyBcdWFjMWNcdWM3NTggXHViMmU4XHVjNWI0XHViNGU0XHVjNzc0IFx1YzIxOFx1Yjg1ZFx1YjQyMFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOFx1Yzc1OCBcdWFjMWNcdWMyMTggbigxICZsZTsgbiAmbGU7IDEwIDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUzMFx1Y2QwOCBcdWM1YjRcdWQ3MThcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzRcdWMwYzEgNDBcdWM3NzRcdWQ1NTggXHVjNzc0XHViYTcwIFx1YzE4Y1x1YmIzOFx1Yzc5MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI2MTBcdWQ1NWMgXHVjOTAwXHVhZGRjXHViMjk0IFx1YjllNFx1YzZiMCBcdWFjOGNcdWM3NDRcdWI3ZWNcdWMxMWMgXHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOCBcdWJhYTlcdWI4NWRcdWM1ZDAgXHVjOTExXHViY2Y1XHViNDFjIFx1YjJlOFx1YzViNFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhYzgwXHVjMGFjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjOGZjXHVjNzU4XHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3MFx1YjlkMFx1YzViNFx1YjMwMFx1YzBhY1x1YzgwNFx1YzVkMCBcdWMyMThcdWI4NWRcdWI0MjAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNDk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGljdGlvbmFyeSBTaXplIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZ292ZXJubWVudCBvZiBEaXNsZWtzaWsgUGlwbGUmcnNxdW87cyBSaXB1Ymx5YyBoYWQgZGVjaWRlZCB0byBpbXByb3ZlIGxpdGVyYWN5IGxldmVsIG9mIGl0cyBjaXRpemVucy4gVG8gdGhpcyBlbmQsIHRoZSBnb3Zlcm5tZW50IGlzc3VlZCBhIGRlY3JlZSB3aXRoIGEgZnVsbCBsaXN0IG9mIGRpY3Rpb25hcnkgd29yZHMuPFwvcD5cclxuXHJcbjxwPlRoZSBydWxlcyBmb3IgY29uc3RydWN0aW9uIG9mIG5ldyB3b3JkcyB3ZXJlIGFsc28gZ3JlYXRseSBzaW1wbGlcdWZiMDFlZDogYW4gYXBwcm92ZWQgd29yZCBtdXN0IGVpdGhlciBiZSBhIGRpY3Rpb25hcnkgd29yZCBvciBjb25zaXN0IG9mIHR3byBwYXJ0cywgd2hlcmUgdGhlIFx1ZmIwMXJzdCBwYXJ0IG11c3QgYmUgYSBkaWN0aW9uYXJ5IHdvcmQgb3IgaXRzIG5vbi1lbXB0eSBwcmVcdWZiMDF4LCBhbmQgdGhlIHNlY29uZCBwYXJ0ICZuZGFzaDsgYSBkaWN0aW9uYXJ5IHdvcmQgb3IgaXRzIG5vbi1lbXB0eSBzdVx1ZmIwM3guPFwvcD5cclxuXHJcbjxwPlRoZSBJbnN0aXR1dGUgb2YgTGFuZ3VhZ2UgU2ltcGxpXHVmYjAxY2F0aW9uIGhhcyBhc3NpZ25lZCB5b3UgdGhlIHRhc2sgdG8gY291bnQgdGhlIG51bWJlciBvZiBkaVx1ZmIwMGVyZW50IGFwcHJvdmVkIHdvcmRzIHRoYXQgY2FuIGJlIGNvbnN0cnVjdGVkIGZyb20gdGhlIGdpdmVuIGRpY3Rpb25hcnkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgZGljdGlvbmFyeSB3b3JkcyBuICgxICZsZTsgbiAmbGU7IDEwIDAwMCkuIFRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWluIGRpY3Rpb25hcnkgd29yZHMsIG9uZSB3b3JkIHBlciBsaW5lLiBEaWN0aW9uYXJ5IHdvcmRzIGFyZSBjb21wb3NlZCBvZiBsb3dlcmNhc2UgTGF0aW4gbGV0dGVycyBhbmQgYXJlIGF0IGxlYXN0IDEgYW5kIGF0IG1vc3QgNDAgbGV0dGVycyBpbiBsZW5ndGguPFwvcD5cclxuXHJcbjxwPlRoZSBJbnN0aXR1dGUgb2YgTGFuZ3VhZ2UgU2ltcGxpXHVmYjAxY2F0aW9uIGRpZCBub3QgbmVjZXNzYXJ5IGRvIGEgZ29vZCBqb2Igb2YgY2xlYW5pbmcgdGhlIGlucHV0IGRhdGEsIHNvIHRoZWlyIGxpc3QgbWF5IGNvbnRhaW4gZHVwbGljYXRlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IFx1ZmIwMWxlIG11c3QgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyICZuZGFzaDsgdGhlIG51bWJlciBvZiBkaVx1ZmIwMGVyZW50IGFwcHJvdmVkIHdvcmRzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==