Similar Words

비어 있지 않은 영문 소문자 수열을 단어라고 하자. 단어 x의 접두사는 x의 마지막 글자를 제거하지 않거나 하나 이상 제거하여 얻을 수 있는 단어 y이다.

두 단어 중 한 단어의 첫 글자를 제거하여 다른 단어를 얻을 수 있으면, 이 두 단어를 유사하다고 하자.

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

• X의 각 단어는 S에 속한 어떤 단어의 접두사이다;
• X에는 유사한 두 단어가 없다.

입력 데이터에는 여러 테스트 케이스가 포함된다. 입력 데이터의 첫 번째 줄에는 테스트 케이스의 수인 정수 t가 주어진다. 이어서 테스트 케이스에 대한 설명이 주어진다.

각 설명의 첫 번째 줄에는 집합 S에 속한 단어의 수인 정수 n가 주어진다 (1 ≤ n ≤ 106). 이어지는 n개의 각 줄에는 S의 원소인 비어 있지 않은 단어 하나가 주어진다. S의 모든 단어는 서로 다르다.

하나의 입력 데이터에 포함된 모든 단어의 길이의 합은 106을 초과하지 않음이 보장된다.

각 테스트 케이스마다 X에 포함될 수 있는 단어의 최대 개수인 정수 m 하나를 한 줄에 출력한다.