输入数据的第一行包含一个整数 $T$ , 代表测试数据组数。
接下来是 $T$ 组数据。
每组数据的第一行包含三个整数 $n$ , $m$ 和 $k$ 。
接下来 $n-1$ 行,每行包含两个整数 $u$ 和 $v$ ，代表节点 $u$ 和 $v$ 之间有一条树边。

对于每组数据， 输出一行， 包含一个整数， 代表所求的答案。

样例输入

3
2 2 0
1 2
3 3 2
1 3
1 2
3 3 1
1 2
2 3

样例输出

4
2
12

对于所有数据，T≤10,n≤100,k≤100,m≤109 T \leq 10, n \leq 100, k \leq 100, m\leq 10^9T≤10,n≤100,k≤100,m≤10​9​​