#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...) fprintf(stderr, s)

template<class T> inline void amin(T &a, const T &b) { if (b<a) a=b; }
template<class T> inline void amax(T &a, const T &b) { if (a<b) a=b; }
struct UnionFind {
    int n;
    vector<int> U;
    UnionFind() {}
    UnionFind(int n): n(n), U(n, -1) {}
    int root(int x) {
    if (U[x] < 0) return x;
    return U[x] = root(U[x]);
    }
    int link(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return x;
    if (U[y] < U[x]) swap(x, y);
    U[x] += U[y];
    n--;
    return U[y] = x;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size() { return n; }
    int count(int x) { return -U[root(x)]; }
};


int N,  X[111], Y[111];
bool B[111];

bool con() {
    UnionFind U(N);
    REP (i, N+1) if (!B[i]) U.link(X[i], Y[i]);
    return U.count(0) == N;
}

void MAIN() {
    scanf("%d", &N);
    REP (i, N+1) {
    scanf("%d%d", X+i, Y+i);
    X[i]--; Y[i]--;
    }
    memset(B, 0, sizeof B);

    int ans = 0;
    REP (i, N+1) {
    B[i] = true;
    if (con()) {
        ans++;
        REP (j, i) {
        B[j] = true;
        if (con()) ans++;
        B[j] = false;
        }
    }
    B[i] = false;
    }

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

int main() {
    int T;
    scanf("%d", &T);
    REP (i, T) MAIN();
    return 0;
}