You are given a tree (connected graph without cycles) consisting of $n$ vertices. The tree is unrooted — it is just a connected undirected graph without cycles.

In one move, you can choose exactly $k$ leaves (leaf is such a vertex that is connected to only one another vertex) connected to the same vertex and remove them with edges incident to them. I.e. you choose such leaves $u_1, u_2, \dots, u_k$ that there are edges $(u_1, v)$, $(u_2, v)$, $\dots$, $(u_k, v)$ and remove these leaves and these edges.

Your task is to find the maximum number of moves you can perform if you remove leaves optimally.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $1 \le k < n$) — the number of vertices in the tree and the number of leaves you remove in one move, respectively. The next $n-1$ lines describe edges. The $i$-th edge is represented as two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$), where $x_i$ and $y_i$ are vertices the $i$-th edge connects. It is guaranteed that the given set of edges forms a tree.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.


-----Example-----
Input
4
8 3
1 2
1 5
7 6
6 8
3 1
6 4
6 1
10 3
1 2
1 10
2 3
1 5
1 6
2 4
7 10
10 9
8 10
7 2
3 1
4 5
3 6
7 4
1 2
1 4
5 1
1 2
2 3
4 3
5 3

Output
2
3
3
4



-----Note-----

The picture corresponding to the first test case of the example:

[Image]

There you can remove vertices $2$, $5$ and $3$ during the first move and vertices $1$, $7$ and $4$ during the second move.

The picture corresponding to the second test case of the example:

[Image]

There you can remove vertices $7$, $8$ and $9$ during the first move, then vertices $5$, $6$ and $10$ during the second move and vertices $1$, $3$ and $4$ during the third move.

The picture corresponding to the third test case of the example:

$\text{of}$

There you can remove vertices $5$ and $7$ during the first move, then vertices $2$ and $4$ during the second move and vertices $1$ and $6$ during the third move.

Difficulty: introductory

Starter code:

Solutions:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

for _ in range(val()):
    n, k = li()
    d = defaultdict(set)
    for i in range(n-1):
        a, b = li()
        d[a].add(b)
        d[b].add(a)
    thistime = 1
    he = deque()
    visited = {}
    for i in d:
        if len(d[i]) == 1:
            visited[i] = 1
            he.append(i)
    ans = 0
    counts = defaultdict(int)
    # print(he)

    while he:
        i = he.popleft()
        for j in list(d[i]):
            counts[j] += 1
            d[i].remove(j)
            d[j].remove(i)
            if counts[j] == k:
                thistime = 1
                ans += 1
                counts[j] = 0
                if len(d[j]) == 1:
                    if j not in visited:he.append(j)
                    visited[j] = 1
                    # print(j, he)
    print(ans)

import sys
input = sys.stdin.readline
for f in range(int(input())):
    n,k=map(int,input().split())

    neig=[0]*n
    for i in range(n):
        neig[i]=[0]

    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        neig[a][0]+=1
        neig[b][0]+=1
        neig[a].append(b)
        neig[b].append(a)
    conleaves=[0]*n
    for i in range(n):
        conleaves[i]=[0]
    goodvertices=[]
    mx=0
    for i in range(n):
        if neig[i][0]==1:
            if neig[neig[i][1]][0]>0:
                conleaves[neig[i][1]][0]+=1
                conleaves[neig[i][1]].append(i)
                neig[i][0]=0
                if conleaves[neig[i][1]][0]==k:
                    goodvertices.append(neig[i][1])
    while len(goodvertices)>0:
        v=goodvertices.pop()
        rem=conleaves[v][0]//k
        mx+=rem
        rest=conleaves[v][0]%k
        conleaves[v]=conleaves[v][0:rest+1]
        conleaves[v][0]=rest
        neig[v][0]-=rem*k
        if neig[v][0]==1:
            for i in range(1,len(neig[v])):
                if neig[neig[v][i]][0]>0:
                    neig[v][0]=0
                    conleaves[neig[v][i]][0]+=1
                    conleaves[neig[v][i]].append(v)
                    if conleaves[neig[v][i]][0]==k:
                        goodvertices.append(neig[v][i])
    print(mx)

def crop_set(s, n):
    new = set()
    it = iter(s)
    for i in range(n):
        new.add(next(it))
    return new


class Vertex:
    __slots__ = ("vertexes", "leaves", "graph")

    def __init__(self, graph):
        self.vertexes = set()
        self.leaves = 0
        self.graph = graph

    def try_to_leave(self):
        if len(self.vertexes) + self.leaves == 1:
            if self.vertexes:
                parent = self.vertexes.pop()
                parent.vertexes.remove(self)
                parent.leaves += 1
                parent.update()
                self.vertexes.add(parent)

    def update(self):
        self.graph[self] = self.leaves


class Tree:
    def __init__(self, n, k):
        self.k = k
        self.lc = [set() for _ in range(n // k + 1)]
        self.dlc = dict()
        self.max = 0

    def add_vertex(self, v):
        self.dlc[v] = 0
        self.lc[0].add(v)
        v.update()

    def __setitem__(self, key, value):
        value = value // self.k

        if self.max == self.dlc[key] > value:
            self.lc[self.max].discard(key)
            while not self.lc[self.max]:
                self.max -= 1
        else:
            self.lc[self.dlc[key]].discard(key)

        if value > self.max:
            self.max = value
        self.dlc[key] = value
        self.lc[value].add(key)


def to_int_decrement(s):
    return int(s) - 1


def solve():
    n, k = list(map(int, input().split()))
    tree = Tree(n, k)
    graph = [Vertex(tree) for _ in range(n)]

    for _ in range(n - 1):
        a, b = list(map(to_int_decrement, input().split()))
        graph[a].vertexes.add(graph[b])
        graph[b].vertexes.add(graph[a])

    if k == 1:
        print(n - 1)
        return

    for v in graph:
        tree.add_vertex(v)
    for v in graph:
        v.try_to_leave()

    c = 0
    while tree.max > 0:
        v = tree.lc[tree.max].pop()
        c += v.leaves // k
        v.leaves -= v.leaves // k * k
        v.try_to_leave()
        v.update()
    print(c)


for _ in range(int(input())):
    solve()


from sys import stdin, stdout
import functools
import sys,os,math

#sys.setrecursionlimit(10**6)

T = int(input())

for _ in range(T):
    N, K = list(map(int, input().split()))
    DS = [0] * (N + 1)
    LeafNum = [0] * (N + 1)
    g = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = list(map(int, input().split()))
        DS[u] += 1
        DS[v] += 1
        g[u].append(v)
        g[v].append(u)

    for u in range(1, N+1):
        if DS[u] == 1:
            for v in g[u]:
                LeafNum[v] += 1
    
    if K == 1:
        print(N - 1)
        continue

    q = set()
    for u in range(1, N+1):
        if LeafNum[u] >= K:
            q.add(u)
    
    ans = 0
    while len(q) > 0:
        u = q.pop()
        nl = LeafNum[u]
        ans += int(nl / K)
        LeafNum[u] = nl % K
        dn = int(nl / K) * K
        DS[u] -= int(nl / K) * K
        if DS[u] == 1:
            for v in g[u]:
                if DS[v] == 1 and dn > 0:
                    dn -= 1
                    continue

                LeafNum[v] += 1
                if LeafNum[v] >= K and v not in q:
                    q.add(v)
    print(ans)
    



        



def main():
    from heapq import heapify, heappop, heappush
    import sys
    input = sys.stdin.readline
    for __ in [0]*int(input()):
        N, K = list(map(int, input().split()))

        G = [[] for _ in [0]*N]
        deg = [0]*N
        for _ in [0]*(N-1):
            a, b = list(map(int, input().split()))
            a -= 1
            b -= 1
            G[a].append(b)
            G[b].append(a)
            deg[a] += 1
            deg[b] += 1

        if K == 1:
            print(N-1)
            continue

        leaf = [0]*N

        for v in range(N):
            if deg[v] == 1:
                u = G[v][0]
                leaf[u] += 1

        L = [(-l, v) for v, l in enumerate(leaf) if l >= K]
        heapify(L)

        ans = 0
        while L:
            l, v = heappop(L)
            if -l != leaf[v]:
                continue
            q, r = divmod(-l, K)
            ans += q
            leaf[v] = r
            deg[v] -= K*q

            p = -1
            cnt = 0
            for u in G[v]:
                if deg[u] == 1 and cnt < K*q:
                    cnt += 1
                    deg[u] = 0
                elif deg[u]:
                    p = u
                if cnt == K*q and (deg[v] != 1 or p != -1):
                    break

            if deg[v] == 1:
                if p != -1:
                    leaf[p] += 1
                    if leaf[p] >= K:
                        heappush(L, (-leaf[p], p))
        print(ans)


def __starting_point():
    main()

__starting_point()

def crop_set(s, n):
    new = set()
    it = iter(s)
    for i in range(n):
        new.add(next(it))
    return new


class Vertex:
    __slots__ = ("vertexes", "leaves", "graph")

    def __init__(self, graph):
        self.vertexes = set()
        self.leaves = 0
        self.graph = graph

    def try_to_leave(self):
        if len(self.vertexes) + self.leaves == 1:
            if self.vertexes:
                parent = self.vertexes.pop()
                parent.vertexes.remove(self)
                parent.leaves += 1
                parent.update()
                self.vertexes.add(parent)

    def update(self):
        self.graph[self] = self.leaves


class Tree:
    def __init__(self, n, k):
        self.k = k
        self.lc = [set() for _ in range(n // k + 1)]
        self.dlc = dict()
        self.max = 0

    def add_vertex(self, v):
        self.dlc[v] = 0
        self.lc[0].add(v)
        v.update()

    def __setitem__(self, key, value):
        value = value // self.k

        if self.max == self.dlc[key] > value:
            self.lc[self.max].discard(key)
            while not self.lc[self.max]:
                self.max -= 1
        else:
            self.lc[self.dlc[key]].discard(key)

        if value > self.max:
            self.max = value
        self.dlc[key] = value
        self.lc[value].add(key)


def to_int_decrement(s):
    return int(s) - 1


def solve():
    n, k = map(int, input().split())
    tree = Tree(n, k)
    graph = [Vertex(tree) for _ in range(n)]

    for _ in range(n - 1):
        a, b = map(to_int_decrement, input().split())
        graph[a].vertexes.add(graph[b])
        graph[b].vertexes.add(graph[a])

    if k == 1:
        print(n - 1)
        return

    for v in graph:
        tree.add_vertex(v)
    for v in graph:
        v.try_to_leave()

    c = 0
    while tree.max > 0:
        v = tree.lc[tree.max].pop()
        c += v.leaves // k
        v.leaves -= v.leaves // k * k
        v.try_to_leave()
        v.update()
    print(c)


for _ in range(int(input())):
    solve()

import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    n,k=MI()
    to=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=MI1()
        to[u].append(v)
        to[v].append(u)

    if k==1:
        print(n-1)
        continue

    dp=[0]*n
    beleaf=[False]*n
    leaves=[0]*n
    stack=[(0,-1)]
    first=[True]*n
    while stack:
        u,pu=stack.pop()
        if first[u]:
            first[u]=False
            stack.append((u,pu))
            for v in to[u]:
                if v==pu:continue
                stack.append((v,u))
        else:
            dp[u]=leaves[u]//k
            if pu!=-1 and dp[u]*k+1==len(to[u]):
                leaves[pu]+=1
                beleaf[u]=True
            for v in to[u]:
                if v==pu:continue
                dp[u]+=dp[v]
    """
    print(dp)
    print(leaves)
    print(beleaf)
    """

    stack=[(0,-1)]
    while stack:
        u,pu=stack.pop()
        for v in to[u]:
            if v==pu:continue
            dp[v]=dp[u]
            if (leaves[u]-beleaf[v])%k==0 and (leaves[u]-beleaf[v])+1==len(to[u]):
                leaves[v]+=1
                if leaves[v]%k==0:dp[v]+=1
            stack.append((v,u))
    """
    print(dp)
    print(leaves)
    print(beleaf)
    """
    print(max(dp))