F. Broken Line Operation
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Kronos Agency never leaves loose ends. After an internal leak, director Clara Voss suspects that part of her network of informants has been compromised. The organization consists of agents connected to each other through direct communication channels. By design, the network avoids redundancies: between any pair of agents, there exists a unique possible chain of contacts.

To contain the damage, Clara must activate exactly $$$k$$$ agents. The activated agents will receive a special protocol and will operate in enhanced undercover mode. The rest will remain inactive, under observation.

Each direct channel that connects an activated agent with one that is not activated becomes a critical point of cross-monitoring. These points allow for information verification and detection of possible betrayals. The more there are, the greater the internal control capacity.

Clara needs to decide which agents to activate so that the number of these critical channels is maximum.

Your task is to help her.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

For each case:

  • The first line contains two integers $$$n$$$ and $$$k$$$: the number of agents in the network and the exact number of agents that must be activated.
  • The following $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$, indicating that there is a direct and bidirectional communication channel between agents $$$u$$$ and $$$v$$$.
It is guaranteed that the network is connected and contains no redundancies.
Output

For each case, print a single integer: the maximum number of direct channels that can connect an activated agent with a non-activated one, activating exactly $$$k$$$ agents.

Example
Input
3
3 2
1 2
2 3
5 2
1 2
1 3
1 4
1 5
2 0
1 2
Output
2
3
0
Note
  • $$$1 \le T \le 1000$$$
  • $$$2 \le n \le 2000$$$
  • $$$0 \le k \le n$$$
  • $$$1 \le u, v \le n$$$ and the graph is a tree.
  • The sum of $$$n$$$ over all cases does not exceed $$$2000$$$.