#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <string>

#include <set>

using namespace std;

typedef long long ll;

const int N = 1e2 + 5;

struct DSU  {

    int rt[N];

    DSU()   {

        memset (rt, -1, sizeof (rt));

    }

    int Find(int x) {

        return rt[x] == -1 ? x : rt[x] = Find (rt[x]);

    }

    void Union(int x, int y)    {

        x = Find (x);   y = Find (y);

        if (x == y) return ;

        rt[x] = y;

    }

    bool same(int x, int y) {

        return Find (x) == Find (y);

    }

};

int u[N], v[N];

int main(void)  {

    int T;  scanf ("%d", &T);

    while (T--) {

        int n;  scanf ("%d", &n);

        for (int i=0; i<n+1; ++i)    {

            scanf ("%d%d", u+i, v+i);

        }

        int ans = 0;

        for (int i=0; i<n+1; ++i)   {

            DSU dsu;    int edge = 0;

            for (int j=0; j<n+1; ++j)   {

                if (i == j) continue;

                if (!dsu.same (u[j], v[j]))  {

                    dsu.Union (u[j], v[j]);

                    edge++;

                }

                if (edge == n - 1)  break;

            }

            if (edge == n - 1)  ans++;

        }

        for (int i=0; i<n+1; ++i)   {

            for (int j=i+1; j<n+1; ++j)   {

                DSU dsu;    int edge = 0;

                for (int k=0; k<n+1; ++k)   {

                    if (k == i || k == j)   continue;

                    if (!dsu.same (u[k], v[k]))  {

                        dsu.Union (u[k], v[k]);

                        edge++;

                    }

                    if (edge == n - 1)  break;

                }

                if (edge == n - 1)  ans++;

            }

        }

        printf ("%d\n", ans);

    }

    return 0;

}