小 Q 正在游戏“怪物猎人”中与可怕的怪物战斗。战场由 $n$ 个交叉路口组成，编号为 $1, 2, \dots, n$，由 $n-1$ 条双向道路连接，形成一棵树。小 Q 现在位于交叉路口 1，拥有 $X$ 点生命值（HP）。

除了交叉路口 1 外，每个交叉路口都有一个怪物。当小 Q 第一次移动到第 $k$ 个交叉路口时，他必须与该路口的怪物战斗。在战斗中，他会损失 $a_i$ 点 HP。当他最终击败怪物后，他会获得 $b_i$ 点 HP。注意，当 HP 变为负数（$< 0$）时，游戏结束，因此绝不能让这种情况发生。如果小 Q 多次访问同一个交叉路口，战斗只会在第一次访问时发生，因为怪物没有额外的生命。

当所有怪物都被清除时，小 Q 将赢得游戏。请编写一个程序来计算能够赢得游戏所需的最小初始 HP。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2000$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示交叉路口的数量。

接下来的 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($0 \le a_i, b_i \le 10^9$)，描述交叉路口 $2, 3, \dots, n$ 处的怪物。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示交叉路口 $u$ 和 $v$ 之间的一条双向道路。保证这些道路构成一棵树。

保证所有 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，打印一行包含一个整数，表示赢得游戏所需的最小初始 HP。

样例

输入 1

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

输出 1

3