#include <iostream>


struct animal{
    int delta; //Akik rá mutatnak ennyivel tolni kell
    int setid; //Melyik halmazba tartozik
};

std::ostream& operator<<(std::ostream &os, animal &a){
    std::cout<<"delta: "<<a.delta<<"\n";
    std::cout<<"setid(parent): "<<a.setid<<"\n";
    return os;
}

int m3(int val){
    return ((val%3)+3)%3;
}


class rules{
public:
    rules(int n){
        this->badrule = 0;
        this->n=n;
        animals = new animal[n];
        for(int i = 0; i < n;i++){
            animals[i].setid = i;
            animals[i].delta = 0;
        }
    }

    ~rules(){delete[] animals;}

    bool equal(int a, int b){
        if(a==b)return true;
        if(a>=n||b>=n)return (badrule++,false);

        int roota = getroot(a);
        int rootb = getroot(b);

        int reala = getrealvalue(a);
        int realb = getrealvalue(b);


        if(roota == rootb){
            bool check = reala == realb;
            badrule+=!check;
            return check;
        }else{
            if(reala != realb){
                get(rootb).delta += reala - realb;
            }

            uni(b,a);
            return true;
        }
    }


    bool eat(int a, int b){
        if(a==b)return (badrule++,false);
        if(a>=n||b>=n)return (badrule++,false);


        int roota = getroot(a);
        int rootb = getroot(b);

        int reala = getrealvalue(a);
        int realb = getrealvalue(b);

        if(roota == rootb){
            bool check = reala == m3(realb-1);
            badrule+=!check;
            return check;
        }else{
            if(reala != m3(realb-1)){
                get(rootb).delta += m3(reala+1) - realb;
            }

            uni(b,a);
            return true;
        }
    }



    void debug_info(){
        for(int i = 0;i<n;i++){
            std::cout<<animals[i];
            std::cout<<"root id: "<<getroot(i)<<"\n";
            std::cout<<"real value: "<<getrealvalue(i)<<"\n";
            std::cout<<"----\n";
        }
    }

    int get_delta(int a){
        int sub=0;
        if(animals[a].setid != a){
            sub=get_delta(animals[a].setid);
        }
        return get(a).delta+sub;
    }

    //Végig járja egészen a gyökér elemig, a deltákat összeadja majd eltolja
    int getrealvalue(int a){
        return m3(get_delta(a));
    }

    int getparent(int a){
        return animals[a].setid;
    }

    int getroot(int a){
        if(animals[a].setid != a)
            return getroot(animals[a].setid);
        return a;
    }

    //a-t olvasztja
    void uni(int a, int b){animals[getroot(a)].setid = getroot(b);}

    animal& get(int index){return animals[index];}

    int n;
    int badrule;
    animal * animals;
};


int main(){
    int tcase;
    scanf("%d",&tcase);

    while(tcase--){
        int n,l;
        scanf("%d %d",&n,&l);
        rules r(n);

        int t,a,b;
        while(l--){
            scanf("%d %d %d",&t,&a,&b);
            if(t==1){
                r.equal(a-1,b-1);
            }else{
                r.eat(a-1,b-1);
            }
        }

        printf("%d",r.badrule);
        if(tcase!=0)printf("\n");
    }

    return 0;
}