有一天，我们的孙学长因为“训练过于辛苦”，敲着敲着代码就睡着了。睡梦中，孙学长成了拯救世界的勇士。
孙学长梦中的世界是这样的，n个交叉路口，为1,2,3，...，n，由n-1条双向道路连接着。我们的孙学长现在在交叉路口1，最初有X的血值。
除了孙学长现在所在的交叉路口1，每个交叉路口都有一个大怪兽，大怪兽没有复活的能力，所以被孙学长打败后该路口就没有怪兽了(嘎嘎)，
如果孙学长想要去第k个路口，他必须与这个路口的怪兽斗争。
在斗争中，孙学长会失去ai的血量，当他最终打败怪兽的时候，他会得到bi的血量(不要问问什么，因为这是他的梦，嘤嘤嘤)
我们的孙学长是超级厉害的，所以他一定会打败怪兽。但是，如果孙学长的血量变为负数(<0),他会感觉自己好low(啊哈哈哈)，所以我们的孙学长是不会让这种情况出现的！！！
当孙学长梦到自己像超人一样打败所有怪兽的时候，他被自己的猪队友敲键盘的声音吵醒了，孙学长很不开心，毕竟不是人人都可以当super hero。
为了“惩罚”他，孙学长把自己的梦告诉了他，要求他算出在梦中的自己血量不为负数的情况下，最初需要的血量X最少为多少。
孙学长的猪队友太猪了，机智的你能帮帮他的猪队友算出来吗？
(温馨提示，如果孙学长想去有道路连接的下一个路口，他必须先打败当前路口的怪兽~)

第一行一个数T(1<=T<=2000),表示测试样例的数量。
每一个测试样例中，第一行一个数字n(2<=n<=100000)表示交叉路口的数量。
接下来的n-1行，每行两个数字ai，bi(0<=ai,bi<=10^9),表示第2,3，...，n个路口打败怪兽失去的血量和得到的血量。
再接下来的n-1行，每行两个数字u和v，表示u和v路口之间有道路连接。
保证∑n≤10^6.

对于每一个样例，输出一个单独的数字，表示最初的最小的血量。每个数字占一行。

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

3