RE

#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;

vector< int > adj[1005];
vector< int > child[1005];
bool isVis[1005];
bool isConn[1005];
//vector< int > track;
ll temp = 0;
int k;
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)
{
	//track.pb(s);
	isConn[s] = true;
	isVis[s] = true;
	for(auto x: adj[s]) {
		if(!isVis[x]) {

			child[s].pb(x);
			dfs(x);
		}
	}

	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();
		child[s].pb(s);
		//cout << s << " lol " << endl;
		//temp++;
	}
	else if(sz>k) {
		for(int i=k; i<sz; i++) {
			isConn[child[s][i]] = false;
			child[s].pop();
		}
	}

	return;
}

void solve()
{
	int n;
	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);
	for(int i=1; i<=n; i++) {
		//debug;
		if(isConn[i]) {
			//debug;
			//cout <<  i << " ";
			sum += (ll)child[i].size();
		}
	}
	cout << "Case " << cc++ << ": ";
	cout << sum+temp << endl;
}
int main()
{
	FastIO;
	//freopen("tttt.in", "r", stdin);
	//freopen("tttt.out", "w", stdout);
	int t;
	//t = 1;
	cin >> t;
	while(t--){
		temp = 0;
		memset(isVis, false, sizeof(isVis));
		memset(isConn, false, sizeof(isConn));
		for(int i=0; i<=1004; i++) {
			adj[i].clear();
			child[i].clear();
		}
		solve();
	}
	return 0;
}