#include<iostream>
#include<vector>
#include<cstring>
#include<set>
#define ll unsigned long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10,P=37;
vector<int>e[maxn];
int n,k;
vector<int>e2[maxn];
set<ll>st;
bool vis[maxn];
int siz[maxn];
ll Hash[maxn];
void dfs(int u){
	Hash[u]=u;
	for(int v:e2[u]){
		if(vis[v])continue;
		vis[v]=true;
		dfs(v);
		Hash[u]+=Hash[v]*P;
//		vis[v]=false;
	}
//	cout<<u<<"   "<<Hash[u]<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	int c,T;
	cin>>c>>T;
	while(T--){
		cin>>n>>k;
		for(int i=1;i<=n;++i){
			e[i].clear();
			e2[i].clear();
		}
		for(int i=1;i<n;++i){
			int u,v;
			cin>>u>>v;
			e[u].push_back(i);
			e[v].push_back(i);
		}
		for(int i=1;i<=n;++i){
			for(int x:e[i]){
				for(int y:e[i]){
					if(x==y)continue;
					e2[x].push_back(y);
//					e2[y].push_back(x);
					cout<<x<<' '<<y<<endl;
				}
			}
		}
		st.clear();
		for(int i=1;i<=n-1;++i){
			int x=i;
//			cin>>x;
			memset(vis,false,sizeof(vis));
			memset(Hash,0,sizeof(Hash));
			vis[x]=true;
			dfs(x);
			st.insert(Hash[x]);
//			cout<<st.size()<<endl;
		}
		cout<<st.size()<<endl;
	}
	return 0;
}
/*
7 1
5 2
1 2
1 3
2 4
2 5
1 3




*/
