Parsa has a humongous tree on n vertices.

On each vertex v he has written two integers l_v and r_v.

To make Parsa's tree look even more majestic, Nima wants to assign a number a_v (l_v ≤ a_v ≤ r_v) to each vertex v such that the beauty of Parsa's tree is maximized.

Nima's sense of the beauty is rather bizarre. He defines the beauty of the tree as the sum of |a_u - a_v| over all edges (u, v) of the tree.

Since Parsa's tree is too large, Nima can't maximize its beauty on his own. Your task is to find the maximum possible beauty for Parsa's tree.

Input

The first line contains an integer t (1≤ t≤ 250) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (2≤ n≤ 10^5) — the number of vertices in Parsa's tree.

The i-th of the following n lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 10^9).

Each of the next n-1 lines contains two integers u and v (1 ≤ u , v ≤ n, u≠ v) meaning that there is an edge between the vertices u and v in Parsa's tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case print the maximum possible beauty for Parsa's tree.

Example

Input


3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6


Output


7
8
62

Note

The trees in the example:

<image>

In the first test case, one possible assignment is a = \{1, 8\} which results in |1 - 8| = 7.

In the second test case, one of the possible assignments is a = \{1, 5, 9\} which results in a beauty of |1 - 5| + |5 - 9| = 8
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<map>
#include<stdio.h>
#pragma optimize(2)
#define INF 0x3f3f3f3f
#define ll long long
#define pll pair<ll,ll>
#define pdl pair<double,ll>
#define pdd pair<double, double>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
using namespace std;
const ll N = 2e5 + 5;
/*
每一个点的beauty值大小，只与与其相邻的点的数量有关，能使其与其周围点beauty值达到最大的值a一定是当前点的l,r二者其一
因为：
设p为与当前点相邻且a大于当前点a的点的数量，q为与当前点相邻且a小于当前点a的点的数量
若p>q，那么可以令当前点的a等于l达到最优解，若p<q,可以令当前点的a等于r达到最优解，若p=q，那么a取任何值不会影响答案
令dp[v][0]表示当前点取l，dp[v][1]表示当前点取r
则对与v相邻的每一个孩子u：
dp[v][0]+=max{dp[u][0]+abs(v[l]-u[l]),dp[u][1]+abs(v[l]-u[r])};
dp[v][1]+=max{dp[u][0]+abs(v[r]-u[l]),dp[u][1]+abs(v[r]-u[r])};
*/
ll n;
struct node {
	ll l, r;
	ll dp[2] = { 0 };
}p[N];
ll h[N], e[N], ne[N], idx;
void add(ll a,ll b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
ll dfs(ll cur,ll pre,ll f)
{
	if (p[cur].dp[f] != 0)return p[cur].dp[f];

	for (ll i = h[cur]; i != -1; i = ne[i])
	{
		ll j = e[i];
		if (j == pre)continue;
		if (f == 0) {
			p[cur].dp[0] += max(dfs(j,cur, 0) + abs(p[cur].l - p[j].l), dfs(j,cur, 1) + abs(p[cur].l - p[j].r));
		}
		else
		{
			p[cur].dp[1] += max(dfs(j,cur, 0) + abs(p[cur].r - p[j].l), dfs(j,cur, 1) + abs(p[cur].r - p[j].r));
		}
	}
	//cout << "p[" << cur << "].dp[" << f << "]==" << p[cur].dp[f] << endl;
	return p[cur].dp[f];
}
void solve()
{
	cin >> n;
	memset(h, -1, sizeof h);
	idx = 0;
	for (ll i = 1; i <= n; i++)
	{
		cin >> p[i].l >> p[i].r;
		p[i].dp[0] = 0;
		p[i].dp[1] = 0;
	}
	for (ll i = 1; i <= n - 1; i++)
	{
		ll u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	ll ans = max(dfs(1, -1,0), dfs(1, -1,1));
	cout << ans << endl;
}
int main()
{
	IOS;
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}