Christmas is coming and Bob wants to decorate his tree. The tree has N nodes. 1 is the root. He thinks a tree is beautiful if each node has exactly K child (immediate descendant) nodes (of course except the leaf nodes). He wants to remove zero or more nodes of the tree so that the property holds. If we delete a non-leaf node, the whole subtree rooted in that node, will be removed from the tree. What is the maximum number of nodes the tree can have after deleting some (possibly zero) nodes so that it has the above properties? Input The first line contains T (1 ≤ T ≤ 1000), number of test cases. For each test case, the first line contains two space-separated integers N ( 1 ≤ N ≤ 1000) and K (1 ≤ K ≤ 100). Each of the next N −1 lines contains two integers U and V (1 ≤ U, V ≤ N ), denoting an edge. Output For each case, print the case number and the answer. Sample Input 2 63 12 13 14 45 46 64 12 13 14 45 46 Sample Output Case 1: 4 Case 2: 1