시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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이 하나 주어진다.

출력

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

예제 입력

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

예제 출력

11
3

힌트