Fouad 拥有一份美味的生沙威玛（shawarma），他所在的城市可以表示为一棵无向树。他听说有一个神奇的烤箱可以烹饪沙威玛，使其变得非常美味。然而，为了获得这个神奇的烤箱，该城市必须满足以下两个条件：

• 必须添加一条额外的边来连接树中的两个不同节点（允许连接两个之前已经有直接边相连的节点）。
• 添加新边后，图中桥的数量必须在 $[L, R]$ 的闭区间内。

请帮助 Fouad 计算有多少种添加边的方式可以满足上述条件，从而获得神奇的烤箱。

输入格式

输入文件的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例的第一行包含三个整数 $N, L$ 和 $R$ ($2 \le N \le 10^5, 0 \le L \le R \le N-1$)，其中 $N$ 是节点数，$L$ 和 $R$ 分别是允许的桥的最小和最大数量。

接下来 $N-1$ 行，每行包含两个整数 $X_i$ 和 $Y_i$ ($1 \le X_i, Y_i \le N$)，表示节点 $X_i$ 和 $Y_i$ 之间的一条边。

输出格式

对于每个测试用例，输出一行，包含满足添加新边后图中桥的数量在 $[L, R]$ 闭区间内的方案数。

样例

输入 1

2
5 1 2
1 2
2 3
4 5
2 4
5 1 3
1 2
2 3
4 5
2 4

输出 1

6
10

说明

图中的桥是指这样一条边：如果将其移除，图将变得不连通。

在第二个样例中，结果是通过连接任意两个不同节点得到的。