#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf (-((LL)1<<40))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define dec(i, a, b) for(int i = a; i >= b; i --)

//typedef __int64 LL;
typedef long long LL;
const int MAXN = 4002;
const int MAXM = 110000;
const double eps = 1e-12;
const double PI = 4.0 * atan(1.0);
const int MOD = 1000000007;

struct Edge{
    int u, v, next;
    Edge(int _u = 0, int _v = 0, int _n = 0) {
        u = _u; v = _v; next = _n;
    }
}e[1100];
int head[1100], tot, vis[1100], v[1100];
int n, m, T;

void add_edge(int _u, int _v) {
    e[tot] = Edge(_u, _v, head[_u]);
    head[_u] = tot++;
}

int cnt = 0;

void dfs(int u){
    if(v[u]) return ;
    v[u] = 1;
    cnt ++;
    for (int i = head[u]; i != -1; i = e[i].next) {
        if(vis[i]) continue;
        dfs(e[i].v);
    }
}

int chk()
{
    mem0(v);
    cnt = 0;
    dfs(1);
    return cnt == n;
}

int main()
{
    cin >> T;
    while(T--) {
        cin >> n;
        mem1(head);
        tot = 0;
        m = n + 1;
        int u, v;
        for (int i = 0; i < m; i ++) {
            scanf("%d %d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
        }
        int ans = 0;
        mem0(vis);
        for (int i = 0; i < m * 2; i += 2) {
            vis[i] = vis[i ^ 1] = 1;
            ans += chk();
            for (int j = i; j < m * 2; j += 2) if(i != j) {
                vis[j] = vis[j ^ 1] = 1;
                ans += chk();
                vis[j] = vis[j ^ 1] = 0;
            }
            vis[i] = vis[i ^ 1] = 0;
        }
        cout << ans << endl;
    }
    return 0;
}