#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;

class UnionFindTree{
    struct base_node{
        int parent;
        int rank;
        int size;
    };
    
    vector<base_node> node;
public:
    UnionFindTree(int n){
        node.resize(n);
        for(int i=0; i<n; i++){
            node[i].parent=i;
            node[i].rank=0;
            node[i].size=1;
        }
    }

    int find(int x){  //return root node of x
        if(node[x].parent == x) return x;
        else{
            return node[x].parent = find(node[x].parent);
        }
    }
    
    bool same(int x, int y){
        return find(x) == find(y);
    }

    int size(int at){
        return node[find(at)].size;
    }

    void unite(int x, int y){
        x = find(node[x].parent);
        y = find(node[y].parent);

        if(x==y) return;

        if(node[x].rank < node[y].rank){
            node[x].parent = y;
            node[y].size += node[x].size;
        }else if(node[x].rank > node[y].rank){
            node[y].parent = x;
            node[x].size += node[y].size;
        }else{
            node[x].rank++;
            unite(x,y);
        }
    }
};

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        cin >> n;

        vector<vector<int> > G(n);
        vector<int> u(n+1),v(n+1);

        for(int i=0; i<n+1; i++){
            cin >> u[i] >> v[i];
            u[i]--; v[i]--;
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }

        int ans = 0;
        for(int i=0; i<n+1; i++){
            UnionFindTree uft(n);
            for(int j=0; j<n+1; j++){
                if(j==i) continue;
                uft.unite(u[j], v[j]);
            }
            if(uft.size(0) == n) ans++;
        }
        for(int i=0; i<n+1; i++){
            for(int j=i+1; j<n+1; j++){
                UnionFindTree uft(n);

                for(int k=0; k<n+1; k++){
                    if(k==i || k==j) continue;
                    uft.unite(u[k], v[k]);
                }

                if(uft.size(0) == n) ans++;
            }
        }

        cout << ans << endl;

    }
    return 0;
}