WA khaitsi ekhon :)

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define F first
#define S second
typedef long long ll;
typedef vector< int > vi;
typedef map<int, int > mp;
#define debug cout << -1 << endl;
#define REP(i, a, b) for(int i=a; i<b; i++)
#define pop pop_back
const ll MOD = 1000000007;
int cc = 1;
const int maxN = 2001;
vector< int > adj[maxN];
vector< int > child[maxN];
bool isVis[maxN] = {false};
bool isConn[maxN] = {false};
map< int , int > m;
bool cmp(int a, int b)
{
	if(child[a].size()==child[b].size()) return a<b;
	return child[a].size() > child[b].size();
}

void dfs(int s, int k)
{
	//track.pb(s);
	isConn[s] = true;
	isVis[s] = true;
	for(auto x: adj[s]) {
		if(!isVis[x]) {
			child[s].pb(x);
			dfs(x, k);
		}
	}

	sort(child[s].begin(), child[s].end(), cmp);
	int sz = child[s].size();
	if(sz<k && sz!=0){
		//cout << "** " << s << " ** " << sz << endl;
		//isConn[s];
		for(auto x: child[s]) {
			isConn[x] = false;
		}
		child[s].clear();
		m[s]++;
		//cout << s << " lol " << endl;
		//temp++;
	}
	else if(sz>k) {
		for(int i=sz; i>=k; i--) {
			isConn[child[s][i]] = false;
			child[s].pop();
		}
	}

	return;
}

void solve()
{
	int n, k;
	cin >> n >> k;
	for(int i=0; i<n-1; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	ll sum = 0;
	dfs(1, k);
	for(int i=1; i<maxN; i++) {
		//debug;
		if(isConn[i]) {
			//debug;
			//cout <<  i << " ";
			ll sz = (ll)child[i].size();
			if(sz==0) {
				if(m[i]) sz++;
			}
			sum += sz;
		}
	}
	cout << "Case " << cc++ << ": ";
	cout << sum << endl;
}
int main()
{
	FastIO;
	//freopen("tttt.in", "r", stdin);
	//freopen("tttt.out", "w", stdout);
	int t;
	//t = 1;
	cin >> t;
	while(t--){
		for(int i=0; i<maxN; i++) {
			isConn[i] = false;
			isVis[i] = false;
			adj[i].clear();
			child[i].clear();
		}
		solve();
	}
	return 0;
}