#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
#include <string>
using namespace std;
//a nice problem that I solved in my sleep.
int r=0;
int k;
int parent[200001]={0};
int ans=0;
int count1[200001]={0};
void DFS1(int v, int par, vector<vector<int>> &adj, map<pair<int, int>, bool> &ok)
{
	parent[v]=par;
	int n = adj.size();
	n--;
	if (adj[v].size()==1 && v!=1)
	{
		ok[{v, par}] = 1;
		return;
	}
	int cnt=0;
	bool kk = 1;
	for (int j=0; j<adj[v].size(); j++)
	{
		int u=adj[v][j];
		if (u==par) continue;
		DFS1(u, v, adj, ok);
		if (ok[{u, v}]) cnt++;
		else kk = 0;
		
	}
	r+=cnt/k;
	if (kk) 
	{
		if (cnt % k == 0)
		{
			ok[{v, par}]=1;
		}
	}
	return;
}
void DFS2(int v, int par, vector<vector<int>>& adj, map<pair<int, int>, bool>& ok, vector<int>& moves)
{
	if (par)
	{
		moves[v]+=moves[par];
		moves[v] -= count1[par]/k;
		bool kkpar=0;
		int cnt=0;
		cnt = count1[par] - ok[{v, par}];
		if (cnt == (int)adj[par].size() - 1)
		{
			kkpar = 1;
		}
		if (kkpar)
		{
			if (cnt%k==0)
			{
				kkpar=1;
			}
			else
			{
				kkpar=0;
			}
		}
		moves[v] += cnt / k;
		ok[{par, v}]=kkpar;
		int c=0;
		int c2 = 0;
		for (int j=0; j<adj[v].size(); j++)
		{
			int u=adj[v][j];
			if (u == par)
			{
				if (ok[{u, v}])
				{
					c2++;
				}
				continue;
			}			
			if (ok[{u, v}])
			{
				c++;
			}			
		}
		moves[v] -= c / k;
		moves[v] += (c + c2) / k;
		count1[v]=c+c2;
		ans=max(ans, moves[v]);
	}
	for (int j = 0; j < adj[v].size(); j++)
	{
		int u = adj[v][j];
		if (u != par)
		{
			DFS2(u, v, adj, ok, moves);			
		}
	}
}
int solve()
{
	map<pair<int, int>, bool> ok;
	r = 0;
	ans=0;
	int n; 
	cin>>n>>k;
	
	vector<vector<int>> adj(n+1);
	for (int j=0; j<n-1; j++)
	{
		int v1, v2; cin>>v1>>v2;
		adj[v1].push_back(v2);
		adj[v2].push_back(v1);
	}
	if (k == 1)
	{
		cout << n - 1 << "\n";
		return 0;
	}
	//ok[{v, par}]=>complete? when v is child of par
	DFS1(1, 0, adj, ok);
	vector<int> moves(n+1, 0);
	moves[1]=r;
	ans=moves[1];
	count1[1] = 0;
	for (int j=0; j<adj[1].size(); j++)
	{
		if (ok[{adj[1][j], 1}])
		{
			count1[1]++;
		}
	}
	
	DFS2(1, 0, adj, ok, moves);
	/*for (int j = 1; j <= n; j++)
	{
		cout << j << "| " << moves[j] << " " << count1[j] << "\n";
	}*/
	cout<<ans<<"\n";
	return 0;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	//t=1;
	while (t--)
	{
		solve();
	}
	
	
	
	return 0;
}