package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if (c >= '0' && c <= '9') || c == '-' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return sign * val
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := in.NextInt()
	ans := make([]byte, 0, t*4)

	for ; t > 0; t-- {
		n := in.NextInt()
		k := in.NextInt()

		g := make([][]int, n+1)
		deg := make([]int, n+1)

		for i := 0; i < n-1; i++ {
			u := in.NextInt()
			v := in.NextInt()
			g[u] = append(g[u], v)
			g[v] = append(g[v], u)
			deg[u]++
			deg[v]++
		}

		if k == 0 {
			ans = strconv.AppendInt(ans, int64(n), 10)
			ans = append(ans, '\n')
			continue
		}

		q := make([]int, 0)
		for i := 1; i <= n; i++ {
			if deg[i] <= 1 {
				q = append(q, i)
			}
		}

		rem := n
		for step := 0; step < k && len(q) > 0; step++ {
			rem -= len(q)
			nq := make([]int, 0)
			for _, v := range q {
				deg[v] = 0
				for _, to := range g[v] {
					if deg[to] > 0 {
						deg[to]--
						if deg[to] == 1 {
							nq = append(nq, to)
						}
					}
				}
			}
			q = nq
		}

		ans = strconv.AppendInt(ans, int64(rem), 10)
		ans = append(ans, '\n')
	}

	out.Write(ans)
}