어떤 서비스에서는 두 사용자가 새로 관계를 맺는 사건들이 시간 순서대로 기록된다.

두 사용자가 관계를 맺으면, 두 사람이 속해 있던 무리는 하나로 이어진다. 여기서 한 무리란 관계들을 따라 이동하여 서로 도달할 수 있는 사용자들의 집합을 말한다.

관계가 하나씩 생길 때마다, 방금 관계를 맺은 두 사용자가 속하게 되는 무리의 크기를 알고자 한다.

관계 기록이 주어졌을 때, 각 관계가 추가된 직후 해당 무리에 포함된 사용자 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 관계의 수 F가 주어진다. 이 값은 100,000을 넘지 않는다.

다음 F개의 줄에는 관계가 생긴 순서대로 주어진다. 각 관계는 두 사용자의 아이디로 이루어져 있다.

아이디는 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

관계가 하나 생길 때마다, 그 두 사람이 속한 무리에 몇 명이 있는지 한 줄에 하나씩 출력한다.

예제 입력 1

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

예제 출력 1

2
3
4
2
2
4