다리와 터널

어떤 날은 캠퍼스가 아주 축축하고, 어떤 날은 아주 춥습니다. 그래서 밖에 나가기보다 실내에 머물고 싶은 날이 있습니다. 이를 위해 캠퍼스 설계자들은 건물들을 터널과 다리로 조금씩 연결해 왔습니다. 연결은 건물을 지을 때 함께 만들기도 하고, 나중에 추가하기도 합니다. 하지만 이 연결망이 항상 완성되어 있는 것은 아니어서, 두 건물 사이를 밖으로 나가지 않고 오갈 수 없는 경우도 있습니다.

새 다리나 터널이 두 건물 사이에 지어질 때마다, 그 연결에서 밖으로 나가지 않고 갈 수 있는 건물의 수, 즉 그 연결이 속하게 된 연결된 그룹에 포함된 건물의 수를 출력하세요.

첫 번째 줄에는 정수 하나가 주어지며, 이는 이어지는 테스트 케이스의 개수입니다.

각 테스트 케이스는 정수 $n$이 적힌 줄로 시작합니다 ($n \le 100000$). 이는 앞으로 지어질 다리 또는 터널의 개수입니다. 모든 건물은 이미 존재하지만, 테스트 케이스가 시작될 때에는 아직 어떤 다리나 터널도 지어지지 않은 상태입니다. 이어지는 $n$개의 줄에는 연결이 지어지는 순서대로 정보가 주어지며, 각 줄에는 연결되는 두 건물의 이름이 공백 하나로 구분되어 적혀 있습니다. 건물 이름은 최대 20개의 대문자 또는 소문자로 이루어진 문자열이며, 대소문자를 구분합니다.

다리나 터널이 지어질 때마다, 그 연결에서 밖으로 나가지 않고 도달할 수 있는 건물의 수(연결이 추가된 직후 그 연결이 속한 그룹의 크기)를 정수 하나로 한 줄에 출력하세요.