from sys import stdin
 
def getParent(x):
    if parent_dict[x] == x:
        return x
    parent_dict[x] = getParent(parent_dict[x])
    return parent_dict[x]
 
def unionParent1(a, b):
    a = getParent(a)
    b = getParent(b)
    sum = cnt_dict[a] + cnt_dict[b]
    cnt_dict[a] = sum
    cnt_dict[b] = sum
    #더 작은 쪽을 부모로 갖는다
    if a > b:
        parent_dict[a] = b
    else:
        parent_dict[b] = a
    return
 
def unionParent2(a, b): #a가 b의 부모인 것을 전제로 할 때
    a = getParent(a)
    b = getParent(b)
    if a != b:
        parent_dict[b] = a
        cnt_dict[a] += cnt_dict[b]
    return
 
t = int(stdin.readline()) #number of test cases
for i in range(t):
    f = int(stdin.readline()) #number of friendships formed
    #부모를 저장하는 딕셔너리와 같은 네트워크 친구 수를 저장하는 딕셔너리
    parent_dict, cnt_dict = dict(), dict()
    for j in range(f):
        name1, name2 = stdin.readline().split()
        #입력받은 이름이 딕셔너리에 없는 경우 저장
        if name1 not in parent_dict:
            parent_dict[name1] = name1
            cnt_dict[name1] = 1
        if name2 not in parent_dict:
            parent_dict[name2] = name2
            cnt_dict[name2] = 1
        #부모를 합친다
        #unionParent2(name1, name2)
        unionParent1(name1, name2) #이 함수를 이용하면 출력초과가 뜬다
 
        #같은 네트워크의 친구 수를 출력
        print(cnt_dict[getParent(name1)])

ZnJvbSBzeXMgaW1wb3J0IHN0ZGluCgpkZWYgZ2V0UGFyZW50KHgpOgogICAgaWYgcGFyZW50X2RpY3RbeF0gPT0geDoKICAgICAgICByZXR1cm4geAogICAgcGFyZW50X2RpY3RbeF0gPSBnZXRQYXJlbnQocGFyZW50X2RpY3RbeF0pCiAgICByZXR1cm4gcGFyZW50X2RpY3RbeF0KCmRlZiB1bmlvblBhcmVudDEoYSwgYik6CiAgICBhID0gZ2V0UGFyZW50KGEpCiAgICBiID0gZ2V0UGFyZW50KGIpCiAgICBzdW0gPSBjbnRfZGljdFthXSArIGNudF9kaWN0W2JdCiAgICBjbnRfZGljdFthXSA9IHN1bQogICAgY250X2RpY3RbYl0gPSBzdW0KICAgICPrjZQg7J6R7J2AIOyqveydhCDrtoDrqqjroZwg6rCW64qU64ukCiAgICBpZiBhID4gYjoKICAgICAgICBwYXJlbnRfZGljdFthXSA9IGIKICAgIGVsc2U6CiAgICAgICAgcGFyZW50X2RpY3RbYl0gPSBhCiAgICByZXR1cm4KCmRlZiB1bmlvblBhcmVudDIoYSwgYik6ICNh6rCAIGLsnZgg67aA66qo7J24IOqyg+ydhCDsoITsoJzroZwg7ZWgIOuVjAogICAgYSA9IGdldFBhcmVudChhKQogICAgYiA9IGdldFBhcmVudChiKQogICAgaWYgYSAhPSBiOgogICAgICAgIHBhcmVudF9kaWN0W2JdID0gYQogICAgICAgIGNudF9kaWN0W2FdICs9IGNudF9kaWN0W2JdCiAgICByZXR1cm4KCnQgPSBpbnQoc3RkaW4ucmVhZGxpbmUoKSkgI251bWJlciBvZiB0ZXN0IGNhc2VzCmZvciBpIGluIHJhbmdlKHQpOgogICAgZiA9IGludChzdGRpbi5yZWFkbGluZSgpKSAjbnVtYmVyIG9mIGZyaWVuZHNoaXBzIGZvcm1lZAogICAgI+u2gOuqqOulvCDsoIDsnqXtlZjripQg65SV7IWU64SI66as7JmAIOqwmeydgCDrhKTtirjsm4ztgawg7Lmc6rWsIOyImOulvCDsoIDsnqXtlZjripQg65SV7IWU64SI66asCiAgICBwYXJlbnRfZGljdCwgY250X2RpY3QgPSBkaWN0KCksIGRpY3QoKQogICAgZm9yIGogaW4gcmFuZ2UoZik6CiAgICAgICAgbmFtZTEsIG5hbWUyID0gc3RkaW4ucmVhZGxpbmUoKS5zcGxpdCgpCiAgICAgICAgI+yeheugpeuwm+ydgCDsnbTrpoTsnbQg65SV7IWU64SI66as7JeQIOyXhuuKlCDqsr3smrAg7KCA7J6lCiAgICAgICAgaWYgbmFtZTEgbm90IGluIHBhcmVudF9kaWN0OgogICAgICAgICAgICBwYXJlbnRfZGljdFtuYW1lMV0gPSBuYW1lMQogICAgICAgICAgICBjbnRfZGljdFtuYW1lMV0gPSAxCiAgICAgICAgaWYgbmFtZTIgbm90IGluIHBhcmVudF9kaWN0OgogICAgICAgICAgICBwYXJlbnRfZGljdFtuYW1lMl0gPSBuYW1lMgogICAgICAgICAgICBjbnRfZGljdFtuYW1lMl0gPSAxCiAgICAgICAgI+u2gOuqqOulvCDtlansuZzri6QKICAgICAgICAjdW5pb25QYXJlbnQyKG5hbWUxLCBuYW1lMikKICAgICAgICB1bmlvblBhcmVudDEobmFtZTEsIG5hbWUyKSAj7J20IO2VqOyImOulvCDsnbTsmqntlZjrqbQg7Lac66Cl7LSI6rO86rCAIOucrOuLpAoKICAgICAgICAj6rCZ7J2AIOuEpO2KuOybjO2BrOydmCDsuZzqtawg7IiY66W8IOy2nOugpQogICAgICAgIHByaW50KGNudF9kaWN0W2dldFBhcmVudChuYW1lMSldKQ==

MQoxMAphIGIKYSBjCmEgZAphIGUKYiBjCmIgZApiIGUKYyBkCmMgZQpkIGUK

1
10
a b
a c
a d
a e
b c
b d
b e
c d
c e
d e