강력한 문자열

참고: 이는 문제 Mightier Strings의 (논쟁의 여지는 있지만) 더 쉬운 버전이다. 각 버전에는 $50$점이 배정되어 있음에 유의하라. 두 버전은 문자열이 강력하다는 정의가 약간 다르며, 이 문제에서는 $T$이 더 작다.

$N$개의 문자열(중복을 포함할 수 있음)이 주어지며, 이를 $U$로 나타낸다.

문자열 $S$은 비어 있지 않은 ${|S|+1 \choose 2}$개의 부분 문자열 각각이 (부분 문자열은 문자열의 시작 및/또는 끝에서 영 개 이상의 문자를 삭제하여 얻는 연속된 문자들의 수열이다. 문자열에 적어도 하나의 문자가 있으면 비어 있지 않다.) $U$에 있는 문자열과 같으면 강력하다.

$U$에 있는 문자열 중 강력한 문자열의 개수를 구하여라.

채점

제출한 풀이는 여러 테스트 그룹으로 이루어진 테스트에서 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$3$| $T \leq 100$

$2$ |$10$| $T \leq 10{,}000$

$3$ |$14$| $T \leq 10^5$

$4$ |$23$| 추가 제한 없음.

입력의 첫째 줄에는 문자열의 개수를 나타내는 정수 $N$ ($1 \leq N \leq 10^6$)이 주어진다.

이어지는 $N$개의 줄에는 각각 문자 a-z로 이루어진 비어 있지 않은 문자열이 주어진다. 이 문자열들이 $U$를 이룬다.

$U$에 있는 모든 문자열의 길이의 합을 $T$이라고 하자. $T \leq 10^6$임이 보장된다.

강력한 문자열의 개수를 나타내는 정수를 출력한다.

예제 $1$에서 a은 강력하다. 유일한 부분 문자열이 a이고, 이는 $U$에 있기 때문이다. 마찬가지로 aa도 강력하다. 부분 문자열은 a, a, aa이며, 모두 $U$에 있기 때문이다. 마지막으로 aaa도 강력하다. 부분 문자열 a, a, a, aa, aa, aaa이 모두 $U$에 있기 때문이다.

예제 $2$에서는 abc을 제외한 모든 문자열이 강력하다. abc은 부분 문자열 bc이 $U$에 없으므로 강력하지 않다.