/*
*   author: kartik8800
*/
 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a,b) for(int i = a; i < b; i++)
#define rep(i,a,b) for(int i = a; i < b; i++)
#define mod 1000000007
#define inf (1LL<<60)`
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll,pair<ll,ll>>
#define goog(tno) cout << "Case #" << tno++ <<": "
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define read(x) int x; cin >> x
using namespace std;

template <class T>
class DisjointSetDS{
  unordered_map<T, T> parent;
  // set repr to <set size, set rank> 
  unordered_map<T, pair<int, int>> representativeToSetSpecs;
public:
  void makeSet(T e){
    parent[e] = e;
    representativeToSetSpecs[e] = {1, 0};
  }

  void unionSet(T e1, T e2) {
    T repE1 = find(e1);
    T repE2 = find(e2);
    
    if(repE1 == repE2){
      return;
    }
    
    int rankS1 = representativeToSetSpecs[repE1].second;
    int rankS2 = representativeToSetSpecs[repE2].second;
    
    if(rankS1 > rankS2){
      parent[repE2] = repE1;
      representativeToSetSpecs[repE1].first += 
              representativeToSetSpecs[repE2].first;
      representativeToSetSpecs.erase(repE2);
    }
    
    else {
      parent[repE1] = repE2;
      representativeToSetSpecs[repE2].first += 
              representativeToSetSpecs[repE1].first;
      if(rankS1 == rankS2)
        representativeToSetSpecs[repE2].second++;
      representativeToSetSpecs.erase(repE1);
    }
  }
  
  T find(T e) {
    if(parent[e] == e)
      return e;
    return parent[e] = find(parent[e]);
  }
  
  int sizeOfSet(T e){
    T rep = find(e);
    return representativeToSetSpecs[rep].first;
  }
};

int main() {
   read(t);
   while(t--){
     read(n);
     DisjointSetDS<string> dsu;
     unordered_set<string> friendSeenBefore;
     for(int connect = 0; connect < n; connect++) {
       string friend1, friend2;
       cin >> friend1; cin >> friend2;
       if(friendSeenBefore.find(friend1) == friendSeenBefore.end()){
         dsu.makeSet(friend1);
       }
       if(friendSeenBefore.find(friend2) == friendSeenBefore.end()){
         dsu.makeSet(friend2);
       }
       friendSeenBefore.insert(friend1);
       friendSeenBefore.insert(friend2);
       dsu.unionSet(friend1, friend2);
       cout << dsu.sizeOfSet(friend1) << '\n';
     }
   }
}