1 #include<iostream>
 2 using namespace std;
 3 const int MAX = 200005;
 4 typedef struct set{
 5     int parent;
 6     int num;
 7 }S;
 8 typedef struct node{
 9     int cnt;
10     struct node *next[52];
11 }*tree,Trie;
12 tree root;
13 S sets[MAX];
14 int n,num;
15  
16 inline int GetNum(char *t){//用字典树对字符串编号
17     tree p = root,newnode;
18     for(int i = 0;i < strlen(t); ++i){
19         int u;
20         if(t[i]>='a' && t[i]<='z')
21             u = t[i] - 'a';
22         else u= t[i]-'A'+26;
23         if(p->next[u]==NULL){
24             newnode=(tree)malloc(sizeof(Trie));
25             newnode->cnt=-1;
26             for(int j=0;j<52;j++)
27                 newnode->next[j]=NULL;
28             p->next[u]=newnode;
29             p=newnode;
30         }
31         else
32             p = p->next[u];
33     }
34     if(p->cnt == -1) //该节点未出现过
35         p->cnt = num ++;
36     return p->cnt;
37 }
38  
39 int findParent(int x){
40     if(x != sets[x].parent)
41         sets[x].parent = findParent(sets[x].parent);
42     return sets[x].parent;
43 }
44  
45 inline void init(){
46     root=new Trie;
47     root->cnt=-1;
48     for(int j=0;j<52;j++)
49         root->next[j]=NULL;
50     num=0;
51     for(int i = 0; i < MAX; i++)
52         sets[i].parent = i,sets[i].num = 1;
53 }
54  
55 inline bool Union(int x, int y){
56     x = findParent(x);
57     y = findParent(y);
58     if(x == y)
59         return false;
60     sets[x].parent = y;
61     sets[y].num += sets[x].num;
62     return true;
63 }
64  
65 int main(){
66     int cas;
67     while(scanf("%d", &cas) == 1){
68         while(cas--){
69             init();
70             scanf("%d", &n);
71             int index = 1;
72             for(int i = 0 ; i < n; i++){
73                 char f1[25], f2[25];
74                 int a, b;
75                 scanf("%s %s", f1, f2);
76                 a = GetNum(f1);
77                 b = GetNum(f2);
78                 Union(a, b);
79                 int ans1;
80                 ans1 = findParent(a);
81                 printf("%d\n",sets[ans1].num);
82             }
83         }
84     }
85     return 0;
86 }
87