시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 84 17 16 21.622%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
abc
def
abef

예제 출력 1

60
W3sicHJvYmxlbV9pZCI6IjM0OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWM4MDRcdWM3NTggXHVkMDZjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1YzViOFx1YzViNFx1Yzc3OCAmcXVvdDtcdWM4NzBcdWI5ZDBcdWM1YjQmcXVvdDtcdWI5N2MgXHVjYzNkXHVjODcwXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWM5MDBcdWFkZGNcdWIyOTQgXHVjODcwXHViOWQwXHVjNWI0XHVjNzU4IFx1YWUzMFx1Y2QwOFx1YWMwMCBcdWI0MThcdWIyOTQgXHViMmU4XHVjNWI0XHViOTdjIFx1YmFhOFx1YjQ1MCZuYnNwO1x1YzgwMVx1Yzc0MCBcdWJhYTlcdWI4NWRcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWM3NzQgXHViYWE5XHViODVkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI5N2MmbmJzcDsmcXVvdDtcdWFlMzBcdWNkMDggXHVjNWI0XHVkNzE4JnF1b3Q7XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YWUzMFx1Y2QwOCBcdWM1YjRcdWQ3MThcdWI5N2MmbmJzcDtcdWFjMDBcdWM5YzBcdWFjZTAgXHVjMGM4XHViODVjXHVjNmI0IFx1YjJlOFx1YzViNFx1Yjk3YyZuYnNwO1x1Y2MzZFx1Yzg3MFx1ZDU1OFx1YzVlYyZuYnNwOyZxdW90O1x1Yzg3MFx1YjlkMFx1YzViNFx1YjMwMFx1YzBhY1x1YzgwNCZxdW90O1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVhYzgzXHVjNzc0XHViMmU0LiAmcXVvdDtcdWM4NzBcdWI5ZDBcdWM1YjRcdWIzMDBcdWMwYWNcdWM4MDQmcXVvdDtcdWM1ZDAgXHVjMjE4XHViODVkXHViNDIwIFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjODcwXHVhYzc0Jm5ic3A7XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyZuYnNwO1x1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JnF1b3Q7XHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOCZxdW90O1x1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMmU4XHVjNWI0XHViOTdjIFx1YjQ1MCBcdWJkODBcdWJkODRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjNTVlIFx1YmQ4MFx1YmQ4NFx1Yzc3NCZuYnNwO1x1YWUzMFx1Y2QwOCBcdWM1YjRcdWQ3MThcdWM3NTggXHVjNTVlIFx1YmQ4MFx1YmQ4NChcdWQ2MzlcdWM3NDAgXHVjODA0XHVjY2I0KVx1Yzc3NFx1YWNlMCwgXHViNGI3IFx1YmQ4MFx1YmQ4NFx1Yzc3NCZuYnNwO1x1YWUzMFx1Y2QwOFx1YzViNFx1ZDcxOFx1Yzc1OCBcdWI0YjcgXHViZDgwXHViZDg0KFx1ZDYzOVx1Yzc0MCBcdWM4MDRcdWNjYjQpXHVjNzc0XHViMmU0LiAoXHVjNTVlIFx1YmQ4MFx1YmQ4NFx1YWNmYyBcdWI0YjcgXHViZDgwXHViZDg0XHVjNzQwIHByZWZpeFx1YzY0MCBzdWZmaXhcdWI4NWMgXHVjNzc0XHVkNTc0XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3OCBcdWM4NzBcdWI5ZDBcdWM1YjRcdWIzMDBcdWMwYWNcdWM4MDRcdWM1ZDBcdWIyOTQgXHVjZDFkIFx1YmE4NyBcdWFjMWNcdWM3NTggXHViMmU4XHVjNWI0XHViNGU0XHVjNzc0IFx1YzIxOFx1Yjg1ZFx1YjQyMFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOFx1Yzc1OCBcdWFjMWNcdWMyMTggbigxICZsZTsgbiAmbGU7IDEwIDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUzMFx1Y2QwOCBcdWM1YjRcdWQ3MThcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzRcdWMwYzEgNDBcdWM3NzRcdWQ1NTggXHVjNzc0XHViYTcwIFx1YzE4Y1x1YmIzOFx1Yzc5MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI2MTBcdWQ1NWMgXHVjOTAwXHVhZGRjXHViMjk0IFx1YjllNFx1YzZiMCBcdWFjOGNcdWM3NDRcdWI3ZWNcdWMxMWMgXHVhZTMwXHVjZDA4IFx1YzViNFx1ZDcxOCBcdWJhYTlcdWI4NWRcdWM1ZDAgXHVjOTExXHViY2Y1XHViNDFjIFx1YjJlOFx1YzViNFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhYzgwXHVjMGFjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjOGZjXHVjNzU4XHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3MFx1YjlkMFx1YzViNFx1YjMwMFx1YzBhY1x1YzgwNFx1YzVkMCBcdWMyMThcdWI4NWRcdWI0MjAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzQ5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpY3Rpb25hcnkgU2l6ZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGdvdmVybm1lbnQgb2YgRGlzbGVrc2lrIFBpcGxlJnJzcXVvO3MgUmlwdWJseWMgaGFkIGRlY2lkZWQgdG8gaW1wcm92ZSBsaXRlcmFjeSBsZXZlbCBvZiBpdHMgY2l0aXplbnMuIFRvIHRoaXMgZW5kLCB0aGUgZ292ZXJubWVudCBpc3N1ZWQgYSBkZWNyZWUgd2l0aCBhIGZ1bGwgbGlzdCBvZiBkaWN0aW9uYXJ5IHdvcmRzLjxcL3A+XHJcblxyXG48cD5UaGUgcnVsZXMgZm9yIGNvbnN0cnVjdGlvbiBvZiBuZXcgd29yZHMgd2VyZSBhbHNvIGdyZWF0bHkgc2ltcGxpXHVmYjAxZWQ6IGFuIGFwcHJvdmVkIHdvcmQgbXVzdCBlaXRoZXIgYmUgYSBkaWN0aW9uYXJ5IHdvcmQgb3IgY29uc2lzdCBvZiB0d28gcGFydHMsIHdoZXJlIHRoZSBcdWZiMDFyc3QgcGFydCBtdXN0IGJlIGEgZGljdGlvbmFyeSB3b3JkIG9yIGl0cyBub24tZW1wdHkgcHJlXHVmYjAxeCwgYW5kIHRoZSBzZWNvbmQgcGFydCAmbmRhc2g7IGEgZGljdGlvbmFyeSB3b3JkIG9yIGl0cyBub24tZW1wdHkgc3VcdWZiMDN4LjxcL3A+XHJcblxyXG48cD5UaGUgSW5zdGl0dXRlIG9mIExhbmd1YWdlIFNpbXBsaVx1ZmIwMWNhdGlvbiBoYXMgYXNzaWduZWQgeW91IHRoZSB0YXNrIHRvIGNvdW50IHRoZSBudW1iZXIgb2YgZGlcdWZiMDBlcmVudCBhcHByb3ZlZCB3b3JkcyB0aGF0IGNhbiBiZSBjb25zdHJ1Y3RlZCBmcm9tIHRoZSBnaXZlbiBkaWN0aW9uYXJ5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIGRpY3Rpb25hcnkgd29yZHMgbiAoMSAmbGU7IG4gJmxlOyAxMCAwMDApLiBUaGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbiBkaWN0aW9uYXJ5IHdvcmRzLCBvbmUgd29yZCBwZXIgbGluZS4gRGljdGlvbmFyeSB3b3JkcyBhcmUgY29tcG9zZWQgb2YgbG93ZXJjYXNlIExhdGluIGxldHRlcnMgYW5kIGFyZSBhdCBsZWFzdCAxIGFuZCBhdCBtb3N0IDQwIGxldHRlcnMgaW4gbGVuZ3RoLjxcL3A+XHJcblxyXG48cD5UaGUgSW5zdGl0dXRlIG9mIExhbmd1YWdlIFNpbXBsaVx1ZmIwMWNhdGlvbiBkaWQgbm90IG5lY2Vzc2FyeSBkbyBhIGdvb2Qgam9iIG9mIGNsZWFuaW5nIHRoZSBpbnB1dCBkYXRhLCBzbyB0aGVpciBsaXN0IG1heSBjb250YWluIGR1cGxpY2F0ZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBcdWZiMDFsZSBtdXN0IGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBudW1iZXIgb2YgZGlcdWZiMDBlcmVudCBhcHByb3ZlZCB3b3Jkcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d