파일 검색

대부분의 운영 체제는 하드 드라이브에 있는 파일을 그 내용에 따라 색인(indexing)한다. 각 파일의 내용은 알파벳 소문자로만 이루어진, 비어 있지 않은 문자열이다.

검색을 하려면 검색어가 필요하다. 검색어 역시 알파벳 소문자로만 이루어진, 비어 있지 않은 문자열이다.

검색 결과는 검색어를 부분 문자열로 포함하는 모든 파일의 집합이다.

문자열 $s$가 문자열 $t$의 부분 문자열이라는 것은, $t$ 안에서 $s$가 연속해서 나타난다는 뜻이다. 예를 들어 "foofoo", "cafoo", "foota", "foo"는 모두 "foo"를 부분 문자열로 포함하지만, "foa", "fofo", "fioo", "oofo"는 포함하지 않는다.

하드 드라이브에 있는 모든 파일의 내용을 알고 있다고 하자. 이때 파일들의 어떤 부분 집합이 "검색 가능"한지 알아내려고 한다.

파일들의 부분 집합이 검색 가능하다는 것은, 그 부분 집합을 정확히 검색 결과로 만들어 내는 검색어가 존재한다는 뜻이다.

모든 파일의 내용이 주어졌을 때, 검색 가능한 파일 부분 집합의 개수를 구하는 프로그램을 작성하시오. 부분 집합은 비어 있지 않아야 한다.

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 하드 드라이브에 있는 파일의 개수 $F$가 주어진다 ($1 \le F \le 60$). 다음 $F$개 줄에는 각 파일의 내용이 한 줄에 하나씩 주어진다. 각 파일의 내용은 알파벳 소문자로만 이루어져 있으며, 길이는 최대 $10^4$이다.

입력의 마지막 줄에는 $0$이 하나 주어진다.

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