인류는 우주 공간에 여러 개의 독립적인 우주 정거장 모듈을 건설했다. 초기 상태에는 모든 모듈이 서로 분리되어 독립적으로 작동하고 있다.

중앙 관제실에서는 두 모듈을 안전하게 연결하는 통신 허브 간선 정보들을 순차적으로 접수하고 있다. 두 모듈이 직/간접적으로 연결되어 있다면, 이들은 하나의 '통신 네트워크'를 형성하게 된다.

새로운 통신 허브 연결 정보가 하나씩 들어올 때마다, 해당 연결로 인해 합쳐진 통신 네트워크에 포함된 총 모듈의 개수를 실시간으로 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수 \(T\)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 접수된 통신 허브 연결 정보의 개수 \(F\)가 주어진다.

다음 \(F\)개의 줄에는 하나의 연결 정보를 나타내는 두 모듈의 이름이 공백을 사이에 두고 주어진다.

모듈의 이름은 알파벳 대소문자로만 이루어진 문자열이며, 길이는 1자 이상 20자 이하이다. (대소문자는 구분된다.)

출력

각 테스트 케이스마다, 입력으로 주어지는 허브 연결 정보에 대해 해당 연결이 수행된 직후 두 모듈이 속하게 된 통신 네트워크에 포함된 모듈의 총 개수를 한 줄에 하나씩 출력한다.

만약 이미 같은 네트워크에 속해 있던 두 모듈이 다시 연결 정보로 들어온 경우에도, 현재 속해 있는 네트워크의 전체 모듈 개수를 그대로 출력한다.

제한사항

\((1 \le T \le 10)\)

\((1 \le F \le 100,000)\)

모든 테스트 케이스에서 주어지는 총 연결 정보 \(F\)의 합은 \(200,000\)을 넘지 않는다.

예제 입력 1

1
3
Alpha Beta
Beta Gamma
Alpha Gamma

예제 출력 1

2
3
3

예제 입력 2

2
2
NodeA NodeB
NodeC NodeD
4
Station1 Station2
Station3 Station4
Station2 Station3
Station1 Station4

예제 출력 2

2
2
2
2
4
4