在生日那天,小费迪亚收到了一棵有 $$$n$$$ 顶点的树和一把电锯。他想从中剪出一个连通的子图。 Fedya 决定执行以下操作:他选择三个不同的顶点 $$$a、b、c$$$ ($$$a \lt b \lt c$$$),并剪出包含所有三个顶点的最小连通子图。他希望结果子图的大小为 正是 $$$d$$$(即,剪切子图中的顶点数必须等于$$$d$$$)。
他开始对他可以剪出多少个不同的此类子图感兴趣。如果选择的顶点三元组不同,则子图被认为是不同的。帮他解决这个问题吧!
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$3 \le d \leq n \le 2000$$$) - 树中的顶点数和剪切子图的所需大小。
然后是 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),表示相应边连接的顶点。保证给定的图是一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,输出一个数字——Fedya 可以剪切的不同子图的数量。
示例
输入复制
34 31 23 14 15 51 22 42 35 17 71 21 32 42 53 63 7
输出复制
310
注意
这是第一个测试用例的树的样子:
以下三元组是合适的:($$$1, 2, 3$$$)、($$$1, 2, 4$$$)、($$$1, 3, 4$$$)。但对于三元组 ($$$2, 3, 4$$$),连通子图的大小为 $$$4$$$。
这是第二个测试用例的树的样子:
对于它来说,只有三重顶点 ($$$3, 4, 5$$$) 是合适的。
这是第三个测试用例的树的样子:
可以证明没有三元组适合该子图。