시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 65 15 15 24.194%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력

3
abc
def
abef

예제 출력

60

힌트