#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>

#define ISDIGIT(x) ((x)>='0'&&(x)<='9'?1:0)
#define IS_SPACE_CHARACTER(x) ((x)==' '||(x)=='\t'||(x)=='\n')

using namespace std;

class Stream
{
    char *array,*readHead,*lastEnd;
    int size;

    int getSize()
    {
        int size;
        fseek(stdin,0,SEEK_END);
        size=ftell(stdin);
        rewind(stdin);
        return size;
    }

public:
    Stream()
    {
        this->size=getSize();
        array=new char[size+1];
        size=fread(array,1,size,stdin);
        array[size]=0;
        readHead=array;
        lastEnd=array+size;
    }

    ~Stream()
    {
        size=0;
        if(array!=NULL)
            delete []array;
        array=NULL;
    }

    int nextInt()
    {
        bool minusFlag=false;
        int variable=0;
        for(;!ISDIGIT(*readHead)&&*readHead!='-'&&*readHead;readHead++);
        if(*readHead=='-')
        {
            minusFlag=true;
            readHead++;
        }
        else if(!*readHead)
            throw EOF;
        for(;ISDIGIT(*readHead);readHead++)
            variable=10*variable+*readHead-'0';
        if(minusFlag)
            return -variable;
        return variable;
    }

    void nextWord(char *charArray)
    {
        for(;*readHead&&IS_SPACE_CHARACTER(*readHead);readHead++);
        if(!*readHead)
            throw EOF;
        for(;!IS_SPACE_CHARACTER(*readHead)&&*readHead;readHead++,charArray++)
            *charArray=*readHead;
        *charArray=0;
        if(*readHead)
            readHead++;
    }
};

struct UnionMaker
{
    int parent;
    int rank;
    int treeSize;
}student[1000000];

char people[1000000][22];
vector<int> v[10009];
int vectors[10009];


int unify(int a,int b);
int unionFind(int a);
int hashValue(char *str);
int getIndex(char *name);

int main()
{
    //freopen("a.txt","r",stdin);
    Stream input;

    int vertex,edge,i,s1,s2,totalVectors=0,hashVal,testCase;

    testCase=input.nextInt();

    while(testCase--)
    {
        vertex=0;
        edge=input.nextInt();

        for(i=0;i<totalVectors;i++)
            v[vectors[i]].clear();

        for(i=0;i<vertex;i++)
        {
            input.nextWord(people[i]);
            hashVal=hashValue(people[i]);
            vectors[i]=hashVal;
            v[hashVal].push_back(i);
            student[i].parent=i;
            student[i].rank=0;
            student[i].treeSize=1;
        }

        while(edge--)
        {
            input.nextWord(people[vertex]);
            hashVal=hashValue(people[vertex]);
            s1=getIndex(people[vertex]);
            if(s1==-1)
            {
                v[hashVal].push_back(vertex);
                vectors[vertex]=hashVal;
                student[vertex].parent=vertex;
                student[vertex].rank=0;
                student[vertex].treeSize=1;
                s1=vertex;
                vertex++;
            }
            input.nextWord(people[vertex]);
            hashVal=hashValue(people[vertex]);
            s2=getIndex(people[vertex]);
            if(s2==-1)
            {
                v[hashVal].push_back(vertex);
                vectors[vertex]=hashVal;
                student[vertex].parent=vertex;
                student[vertex].rank=0;
                student[vertex].treeSize=1;
                s2=vertex;
                vertex++;
            }
            printf("%d\n",unify(s1,s2));
        }
        totalVectors=vertex;
    }
    return 0;
}

int unify(int a,int b)
{
    int rootA=unionFind(a);
    int rootB=unionFind(b);
    if(rootA!=rootB)
    {
        if(student[rootA].rank<student[rootB].rank)
        {
            student[rootA].parent=rootB;
            student[rootB].treeSize+=student[rootA].treeSize;
            return student[rootB].treeSize;
        }
        if(student[rootA].rank>student[rootB].rank)
        {
            student[rootB].parent=rootA;
            student[rootA].treeSize+=student[rootB].treeSize;
            return student[rootA].treeSize;
        }
        student[rootB].parent=rootA;
        student[rootA].treeSize+=student[rootB].treeSize;
        student[rootA].rank++;
        return student[rootA].treeSize;
    }
    return student[rootA].treeSize;
}

int unionFind(int a)
{
    if(a!=student[a].parent)
        student[a].parent=unionFind(student[a].parent);
    return student[a].parent;
}

int hashValue(char *str)
{
     int len=strlen(str);
     int intLength = len / 4  , k;
     unsigned int sum = 0,mult;
     for (int j = 0; j < intLength; j++)
     {
         mult = 1;
         for (k = 0; k < 4; k++)
         {
             sum += str[4*j+k] * mult;
             mult *= 256;
         }
     }
     mult = 1;
     for (k = intLength*4; k < len ; k++)
     {
         sum += str[k] * mult;
         mult *= 256;
     }

     return sum%10007;
}

int getIndex(char *name)
{
    int key=hashValue(name),total=v[key].size();
    int i;
    for(i=0;i<total;i++)
        if(!strcmp(name,people[v[key][i]]))
            return v[key][i];
    return -1;
}