bool feasible2(int i, UnionFind &uf) {
    int a = A[i];
    bool a_is_half_square = isHalfSquare(a);
    if (a_is_half_square) {
        if (deg[a] > 0 || cnt[a] > 1) return false;
    }
    cnt[a]++;
    seen[num_seen++] = a;
    for (int k = 1; k <= 512; k++) {
        int64_t b = k*k - a;
        if (b == a) continue;
        if (b > 0 && b < MAXN && cnt[b] > 0) {
            if (uf.find(a) == uf.find(b) ||
                uf.find(a+MAXN) == uf.find(b+MAXN)) return false;
            if (isHalfSquare(b)) {
                if (cnt[b] > 1) return false;
                deg[b]++;
            }
            if (a_is_half_square) deg[a]++;
            uf.join(a, b+MAXN);
            uf.join(a+MAXN, b);
        }
    }
    return true;
}

int main(){
    int t,n,cont;
    cin>>t;
    string a,b;
    map<string,int> convers;
    UnionFind u;

    while (t-->0){
        cin>>n;
        int p,q;

        u.reset(2*n+1);
        convers.clear();
        cont = 1;

        for (int i=0;i<n;i++){
            cin>>a>>b;
            if (!convers.count(a))convers[a] = cont++;
            if (!convers.count(b))convers[b] = cont++;
            p = convers[a], q = convers[b];
            u.unionSet(p,q);
            cout<<u.getSize(p)<<endl;
        }
    }
}

  void initPercolate(){
	 int topPseudoVarIndex = dim*dim;
	 int bottomPseudoVarIndex = topPseudoVarIndex +1;
	 Ufobj = new UnionFind(dim*dim+2); /* 0 to dim*dim -1 is regular grid var */
	 for(int i =0;i< dim;i++){ /* top row */
	   Ufobj->DoUnion(topPseudoVarIndex,i);
	 }	
	 for(int i =dim*(dim-1);i< dim*dim;i++){ /* bottom row */
	   Ufobj->DoUnion(bottomPseudoVarIndex,i);
	 }	
  }

void reset2(int k, UnionFind &uf) {
    for (int i = num_seen-1; i >= 0; i--) {
        int a = seen[i];
        cnt[a] = 0;
        deg[a] = 0;
        uf.makeSet(a);
        uf.makeSet(a+MAXN);
    }
    cnt[A[k]] = 1;
    seen[0] = A[k];
    num_seen = 1;
}

void visitTarjan(const Graph &g, int u, int w,
        vector<Query> &qs, vector<int> &color,
        vector<int> &ancestor, UnionFind &uf) {
    ancestor[ uf.root(u) ] = u;
    FOR(e, g[u]) if (e->dst != w) {
        visitTarjan(g, e->dst, u, qs, color, ancestor, uf);
        uf.unionSet( e->src, e->dst );
        ancestor[ uf.root(u) ] = u;
    }
    color[u] = 1;
    FOR(q, qs) {
        int w = (q->v == u ? q->u : q->u == u ? q->v : -1);
        if (w >= 0 && color[w]) q->w = ancestor[ uf.root(w) ];
    }

 /**
  * This method finds the representative element of the UF structure,
  * while performing the path compression.
  * @return the representative UnionFind of the group.
  */
 UnionFind * find(){
     if (parent == nullptr)
         parent = this;
     if (parent != this)
         parent = parent->find();
     return parent;
 }

int kruskal() {
    sort(es, es + E, comp);

    UnionFind *unionfind = new UnionFind();
    unionfind->init(V);
    int res = 0;

    for (int i = 0; i < E; i++) {
        edge e = es[i];
        if (!unionfind->same(e.from, e.to)) {
            unionfind->unite(e.from, e.to);
            res += e.cost;
        }
    }
    return res;
}

    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        UnionFind uni;
        vector<int> res;

        for (int i=0; i<positions.size(); ++i) {
            auto pos = positions[i];
            int r = pos.first;
            int c = pos.second;

            S.insert(positions[i]);
            uni.add(positions[i]);

            if (S.find(pair<int,int>(r-1, c)) != S.end()) {
                uni.merge(pair<int,int>(r-1,c), pair<int,int>(r,c));
            }
            if (S.find(pair<int,int>(r, c+1)) != S.end()) {
                uni.merge(pair<int,int>(r,c+1), pair<int,int>(r,c));
            }
            if (S.find(pair<int,int>(r+1, c)) != S.end()) {
                uni.merge(pair<int,int>(r+1,c), pair<int,int>(r,c));
            }
            if (S.find(pair<int,int>(r, c-1)) != S.end()) {
                uni.merge(pair<int, int>(r, c - 1), pair<int, int>(r, c));
            }
            res.push_back(uni.countSet());
        }
        return res;
    }

int main (int argc, char** argv)
{
    if (argc <=1) { 
        printf("Usage: ./union <problem_number> \n");
        exit(1);
    }

    int problem_no = atoi(argv[1]);
    UnionFind* uf = new UnionFind (10);

    switch(problem_no) {
        case 0:
        case 1:
            uf->type = QFIND;
            printf("Problem number 1: ");
            /* Q1 union find */
            uf->join(1,4);
            uf->join(9,4);
            uf->join(6,8);
            uf->join(2,1);
            uf->join(0,4);
            uf->join(3,7);
            break;
        case 2:
            printf("Problem number 2: ");
            uf->type = WT_QUNION;
             /* Q2 Weighted quick union */
            uf->wt_join(7,9);
            uf->wt_join(9,4);
            uf->wt_join(7,0);
            uf->wt_join(8,1);
            uf->wt_join(3,7);
            uf->wt_join(5,6);
            uf->wt_join(5,1);
            uf->wt_join(3,8);
            uf->wt_join(2,6);
            break;
        default:
            assert(0 && "Invalid problem number");
            break;
    }

    uf->print();
    return 0;
}

void solve() {
    int ans = 0;
    UnionFind uf = UnionFind(N * 3);

    for(int i = 0; i < K; ++i) {
        int x = X[i] - 1, y = Y[i] - 1;
        if(x < 0 || N <= x || y < 0 || N <= y) {
            ++ans;
        }
        else if(D[i] == 1) {
            if(uf.same(3 * x, 3 * y + 1) || uf.same(3 * x, 3 * y + 2))
                ++ans;
            else
                for(int j = 0; j < 3; ++j)
                    uf.unite(3 * x + j, 3 * y + j);
        }
        else {
            if(uf.same(3 * x, 3 * y + 2) || uf.same(3 * x, 3 * y))
                ++ans;
            else
                for(int j = 0; j < 3; ++j)
                    uf.unite(3 * x + j, 3 * y + (j + 1) % 3);
        }
    }
    printf("%d\n", ans);
}

int main() {
  UnionFind uf;
  uf.init(5);

  assert(!uf.is_same_set(1, 3));
  assert(!uf.is_same_set(0, 4));
  assert(uf.no_disjoint_sets() == 5);

  uf.union_set(1, 2);
  uf.union_set(2, 3);
  uf.union_set(3, 4);

  assert(uf.size_of_set(2) == 4);
  assert(!uf.is_same_set(0, 3));
  assert(uf.is_same_set(1, 4));
  assert(uf.no_disjoint_sets() == 2);  

  return 0;
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int tc;
    scanf("%d",&tc);
    while(tc--)
    {
        int no_friends,f,i=0,a,b;
        string str1,str2;
        char f1[21],f2[21];
        scanf("%d",&f);
        map<string,int>names;
        map<string,int>::iterator it;
        UnionFind uf;
        while(f--)
        {
            scanf("%s %s",f1,f2);
            str1=string(f1);
            str2=string(f2);
            if((it=names.find(str1))==names.end())
            {
                names.insert(make_pair(str1,i));
                uf.add(a=i++);
            }
            else a=it->second;
            if((it=names.find(str2))==names.end())
            {
                names.insert(make_pair(str2,i));
                uf.add(b=i++);
            }
            else b=it->second;

            printf("%d\n",uf.union_set(a,b));
        }
    }
    return 0;

}

void Graph::remove_cycles() {
  /* Pouzijeme Kruskaluv algoritmus s implementaci vyuzivajici strukturu
   Unionfind. Zde usnadnen tim, ze vsechny hrany maji stejnou vahu. */
  UnionFind *uf = new UnionFind(vertex_count);
  
  // V matici incidence projdeme vsechny hrany
  for (int i = 0; i < vertex_count; i++) {
    for (int j = i; j < vertex_count; j++) {
      if (!get(i, j))
        continue;
      /* Pokud jsme v ramci doposud prozkoumanych hran nenasli cestu
       mezi i a j, poznamenejme si do unionfind struktury, ze nyni
       uz ji mame. V opacnem pripade vyhodime z grafu hranu mezi i a j,
       at nemame cyklus. */      
      if (!uf->find(i, j)) {
        uf->do_union(i, j);
      } else {
        unset(i, j);
      }
    }
  }
}

UnionFind* crete_union_find(const std::string& file_name)
{
    int size = 0;
    i__pair *int_list = nullptr;

    parse_input_file(file_name,size,&int_list);
    if(int_list != nullptr && size != 0)
    {
        UnionFind *uFind = new UnionFind();
        uFind->printData();
        for(int index = 0; index < size ; index++)
        {
            if(!uFind->is_connected(int_list[index].first_number, int_list[index].second_number))
            {
                uFind->m_createUnion(int_list[index].first_number, int_list[index].second_number);
            }
        }
        delete[] int_list;
        return uFind;
    }
    return nullptr;
}

int main(void)
{
    cin.sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    vector<vector<int>> speaker_to_langs(N);
    vector<char> seen_langs(M);

    UnionFind uf;
    uf.Init(M);

    
    REP(n,N) {
        int k;
        cin >> k;
        vector<int> langs(k);
        REP(k1,k) {
            int l;
            cin >> l; --l;
            langs[k1] = l;
            seen_langs[l] = 1;
        }

	void executar(SolucaoEdgeSet &s, auxEdgeStruct arestas []) {

		for(int i = 0; i < NUMOBJETIVOS; i++) {
			s.setObj(i,0.0);
		}

		uf.clear();
		
		// coloca NUMEROVERTICES-1 arestas do grafo sem formar ciclo
		int cont = 0, edge = 0;
		while (cont < NUMEROVERTICES-1) {

			// anda ate a proxima aresta que pode ser inserida
			while (uf.sameClass(arestas[edge].a,arestas[edge].b)) edge++;

			// coloca a aresta na solucao
			s.edges[cont][0] = arestas[edge].a;
			s.edges[cont][1] = arestas[edge].b;
			s.setObj(0,s.getObj(0)+f(0,s.edges[cont][0],s.edges[cont][1]));
			s.setObj(1,s.getObj(1)+f(1,s.edges[cont][0],s.edges[cont][1]));
			uf.unionClass( arestas[edge].a, arestas[edge].b );
			cont++;
		}
		// assert (s.confereArestas());
	}

  /// Build tracks for a given series of pairWise matches
  void Build( const PairWiseMatches &  map_pair_wise_matches)
  {
    // 1. We need to know how much single set we will have.
    //   i.e each set is made of a tuple : (imageIndex, featureIndex)
    typedef std::set<indexedFeaturePair> SetIndexedPair;
    SetIndexedPair allFeatures;
    // For each couple of images list the used features
    for (PairWiseMatches::const_iterator iter = map_pair_wise_matches.begin();
      iter != map_pair_wise_matches.end();
      ++iter)
    {
      const size_t & I = iter->first.first;
      const size_t & J = iter->first.second;
      const std::vector<IndMatch> & vec_FilteredMatches = iter->second;

      // Retrieve all shared features and add them to a set
      for( size_t k = 0; k < vec_FilteredMatches.size(); ++k)
      {
        allFeatures.emplace(I,vec_FilteredMatches[k].i_);
        allFeatures.emplace(J,vec_FilteredMatches[k].j_);
      }
    }

    // 2. Build the 'flat' representation where a tuple (the node)
    //  is attached to an unique index.
    map_node_to_index.reserve(allFeatures.size());
    unsigned int cpt = 0;
    for (const auto & feat : allFeatures)
    {
      map_node_to_index.emplace_back(feat, cpt);
      ++cpt;
    }
    // Sort the flat_pair_map
    map_node_to_index.sort();
    // Clean some memory
    allFeatures.clear();

    // 3. Add the node and the pairwise correpondences in the UF tree.
    uf_tree.InitSets(map_node_to_index.size());

    // 4. Union of the matched features corresponding UF tree sets
    for (PairWiseMatches::const_iterator iter = map_pair_wise_matches.begin();
      iter != map_pair_wise_matches.end();
      ++iter)
    {
      const auto & I = iter->first.first;
      const auto & J = iter->first.second;
      const std::vector<IndMatch> & vec_FilteredMatches = iter->second;
      for (const IndMatch & match : vec_FilteredMatches)
      {
        const indexedFeaturePair pairI(I, match.i_);
        const indexedFeaturePair pairJ(J, match.j_);
        // Link feature correspondences to the corresponding containing sets.
        uf_tree.Union(map_node_to_index[pairI], map_node_to_index[pairJ]);
      }
    }
  }

  /// Build tracks for a given series of pairWise matches
  void Build( const matching::PairWiseMatches &  map_pair_wise_matches)
  {
    // 1. We need to know how much single set we will have.
    //   i.e each set is made of a tuple : (imageIndex, featureIndex)
    std::set<indexedFeaturePair> allFeatures;
    // For each couple of images list the used features
    for ( const auto & iter : map_pair_wise_matches )
    {
      const auto & I = iter.first.first;
      const auto & J = iter.first.second;
      const std::vector<matching::IndMatch> & vec_FilteredMatches = iter.second;

      // Retrieve all shared features and add them to a set
      for ( const auto & cur_filtered_match : vec_FilteredMatches )
      {
        allFeatures.emplace(I,cur_filtered_match.i_);
        allFeatures.emplace(J,cur_filtered_match.j_);
      }
    }

    // 2. Build the 'flat' representation where a tuple (the node)
    //  is attached to a unique index.
    map_node_to_index.reserve(allFeatures.size());
    uint32_t cpt = 0;
    for (const auto & feat : allFeatures)
    {
      map_node_to_index.emplace_back(feat, cpt);
      ++cpt;
    }
    // Sort the flat_pair_map
    map_node_to_index.sort();
    // Clean some memory
    allFeatures.clear();

    // 3. Add the node and the pairwise correpondences in the UF tree.
    uf_tree.InitSets(map_node_to_index.size());

    // 4. Union of the matched features corresponding UF tree sets
    for ( const auto & iter : map_pair_wise_matches )
    {
      const auto & I = iter.first.first;
      const auto & J = iter.first.second;
      const std::vector<matching::IndMatch> & vec_FilteredMatches = iter.second;
      for (const matching::IndMatch & match : vec_FilteredMatches)
      {
        const indexedFeaturePair pairI(I, match.i_);
        const indexedFeaturePair pairJ(J, match.j_);
        // Link feature correspondences to the corresponding containing sets.
        uf_tree.Union(map_node_to_index[pairI], map_node_to_index[pairJ]);
      }
    }
  }

    bool argument(int s) {
        memset(&uf, 0, sizeof(uf));
        memset(link, 0, sizeof(link));
        memset(type, 0, sizeof(type));
        q.clear();
        q.push_back(s);
        type[s] = EVEN;

        while (!q.empty()) {
            int u = q.front();
            q.pop_front();

            for (int v : G[u]) {
                if (!type[v]) {
                    type[v] = ODD;
                    link[v] = u;

                    if (match[v]) {
                        type[match[v]] = EVEN;
                        q.push_back(match[v]);
                    } else {
                        int x = v;
                        while (link[x] != s) {
                            int a = link[x];
                            int b = match[a];
                            match[x] = a;
                            match[a] = x;
                            x = b;
                        }

                        match[s] = x;
                        match[x] = s;

                        return true;
                    }
                } else if (type[v] == EVEN &&
                           uf.find(u) != uf.find(v)) {
                    int p = lca(u, v);

                    if (uf.find(u) != p)
                        link[u] = v;
                    if (uf.find(v) != p)
                        link[v] = u;

                    process(u, p);
                    process(v, p);
                }
            }
        }

        return false;
    }

inline void add_node(IntervalTree::Node *x) {
    for (size_t i = 0; i < x->edges.size(); i++) {
        Edge *e = x->edges[i];

        e->idu = uf.find_root(e->u);
        e->idv = uf.find_root(e->v);
        if (e->idu == e->idv) {
            e->idu = e->idv = 0;
            continue;
        }

        uf.link(e->idu, e->idv);
    }
}