비슷한 단어

영소문자로 이루어진 비어 있지 않은 문자열을 단어라고 하자. 단어 $x$의 접두사란 $x$에서 마지막 글자를 0개 이상 제거해 얻을 수 있는 단어 $y$를 말한다.

두 단어가 비슷하다는 것은, 한 단어에서 첫 글자를 제거하면 다른 단어를 얻을 수 있다는 뜻이다.

단어 집합 $S$가 주어진다. 다음 조건을 만족하는 비어 있지 않은 단어 집합 $X$의 최대 크기를 구하라.

• $X$의 모든 단어는 $S$에 속한 어떤 단어의 접두사이다.
• $X$에 비슷한 단어 쌍이 없다.

입력에는 여러 개의 테스트 케이스가 들어 있다. 입력의 첫째 줄에는 테스트 케이스의 개수 $t$가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 집합 $S$에 속한 단어의 개수 $n$이 주어진다 ($1 \le n \le 10^6$). 이어지는 $n$개의 줄에는 $S$의 원소인 비어 있지 않은 단어가 한 줄에 하나씩 주어진다. $S$의 모든 단어는 서로 다르다.

한 입력에서 모든 단어의 길이의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 $X$가 가질 수 있는 단어 개수의 최댓값 $m$을 한 줄에 출력한다.