Mạng xã hội giúp mọi người liên kết với nhau, anh ~A~ bạn của anh ~B~, anh ~B~ bạn của anh ~C~ dẫn đến xem anh ~A~ là bạn anh ~C~. Như vậy, nếu dùng một robot nhện bạn có thể xây dựng cho mình một mạng đồ thị kết nối những người bạn với nhau.

Nhiệm vụ của bạn là quan sát các tương tác trên một trang web như vậy và theo dõi kích thước của mạng của mỗi người.

Input

Dòng thứ nhất chứa một số nguyên ~T~ là số testcase thỏa ~T \le 10~. Mỗi testcase gồm:

• Dòng đầu tiên của mỗi testcase chứa số nguyên ~F~ là số người cần theo dõi thỏa ~1 \le F \le 100000~.

• ~F~ dòng tiếp theo, mỗi dòng chứa tên của hai người cách nhau ký tự trắng với độ dài tên nhỏ hơn ~20~ ký tự alphabet.

Output

Tương ứng với một dòng chứa tên hai người trong mỗi testcase, in số lượng người hiện có trong mạng có mặt của hai người cần quan sát.

Samples

Sample Input 1

1
3
Fred Barney
Barney Betty
Betty Wilma

Sample Output 1

2
3
4