#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int n, k, vis[N];
vector<array<int, 2>> el;
vector<int> g[N];

int dfs(int x)
{
	assert(0 < x && x < N);
	if (vis[x]) return 0;
	vis[x] = true;
	int res = 1;
	for (int y : g[x]) res += dfs(y);
	return res;
}

void solve()
{
	cin >> n >> k;
	el.clear();
	for (int i = 1, u, v; i <= n - 1; i++) cin >> u >> v, el.push_back({u, v});
	int cnt = 0;
	for (int i = 0; i < (1 << n - 1); i++)
	{
		for (int j = 1; j <= n; j++) vis[j] = false, g[j].clear();
		for (int j = 0; j < n - 1; j++)
			if (i & (1 << j)) g[el[j][0]].push_back(el[j][1]), g[el[j][1]].push_back(el[j][0]);
		bool flag = true;
		for (int j = 1; j <= n; j++)
		{
			if (vis[j]) continue;
			int res = dfs(j);
			if (res != k && res != k + 1)
			{
				flag = false;
				break;
			}
		}
		cnt += flag;
	}
	cout << cnt << '\n';
}

signed main()
{
	int t; cin >> t;
	while (t--) solve();
}