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
import java.io.*;
import java.util.*;
import java.math.*;
import java.math.BigInteger; 
//import javafx.util.*; 
public final class B
{    
	 static PrintWriter out = new PrintWriter(System.out); 
	static StringBuilder ans=new StringBuilder();
	static FastReader in=new FastReader();
	static ArrayList<Integer> g[];
	static long mod=(long)(1e9+7);
	static int D1[],D2[],par[];
	static boolean set[];
	static int value[];
	static long INF=Long.MAX_VALUE;
	static int N,M;
	static long L[],R[],dp[][];
	static int s=1;
	public static void main(String args[])throws IOException
	{  					
		int T=i();
		outer:while(T-->0)
		{
			int N=i();
			setGraph(N);
			for(int i=1; i<=N; i++)
			{
				L[i]=l();
				R[i]=l();
			}
			for(int i=1; i<N; i++)
			{
				int a=i(),b=i();
				g[a].add(b);
				g[b].add(a);
			}
			f(1,-1);
			out.println(Math.max(dp[0][1], dp[1][1]));
		}
		out.close();
		//print(L);
		//print(R);
		
		//print(dp[0]);
		//print(dp[1]);
		

	}	
	static void f(int n,int p)
	{
		for(int c:g[n])
		{
			if(c!=p)
			{
			f(c,n);
			long a=dp[0][c]+Math.abs(L[c]-L[n]);
			long b=dp[1][c]+Math.abs(R[c]-L[n]);
			dp[0][n]+=Math.max(a, b);
			a=dp[0][c]+Math.abs(L[c]-R[n]);
			b=dp[1][c]+Math.abs(R[c]-R[n]);
			dp[1][n]+=Math.max(a, b);
			}
		}
	}
	static boolean isPalin(char X[])
	{
		int l=0,r=X.length-1;
		while(l<=r)
		{
			if(X[l]!=X[r])return false;
			l++;
			r--;
		}
		return true;
	}

	static boolean isSorted(int A[])
	{
		int N=A.length;
		for(int i=0; i<N-1; i++)
		{
			if(A[i]>A[i+1])return false;
		}

		return true;		
	}
	static int f1(int x,ArrayList<Integer> A)
	{
		int l=-1,r=A.size();
		while(r-l>1)
		{
			int m=(l+r)/2;
			int a=A.get(m);
			if(a<x)l=m;
			else r=m;
		}		
		return l;
	}


	static int ask(int t,int i,int j,int x)
	{
		System.out.println("? "+t+" "+i+" "+j+" "+x);
		return i();
	}

	static int ask(int a)
	{
		System.out.println("? 1 "+a);
		return i();
	}
	static int f(int st,int end,int d)
	{
		if(st>end)return 0;
		int a=0,b=0,c=0;
		if(d>1)a=f(st+d-1,end,d-1);
		b=f(st+d,end,d);
		c=f(st+d+1,end,d+1);
		return value[st]+max(a,b,c);
	}
	static int max(int a,int b,int c)
	{
		return Math.max(a, Math.max(c, b));
	}
	static int value(char X[],char Y[])
	{
		int c=0;
		for(int i=0; i<7; i++)
		{
			if(Y[i]=='1' && X[i]=='0')return -1;
			if(X[i]=='1' && Y[i]=='0')c++;
		}
		return c;
	}
	static boolean isValid(int i,int j)
	{
		if(i<0 || i>=N)return false;
		if(j<0 || j>=M)return false;
		return true;
	}

	static long fact(long N)
	{
		long num=1L;
		while(N>=1)
		{
			num=((num%mod)*(N%mod))%mod;
			N--;
		}
		return num;
	}
	static boolean reverse(long A[],int l,int r)
	{
		while(l<r)
		{
			long t=A[l];
			A[l]=A[r];
			A[r]=t;
			l++;
			r--;
		}
		if(isSorted(A))return true;
		else return false;
	}
	static boolean isSorted(long A[])
	{
		for(int i=1; i<A.length; i++)if(A[i]<A[i-1])return false;
		return true;
	}
	static boolean isPalindrome(char X[],int l,int r)
	{
		while(l<r)
		{
			if(X[l]!=X[r])return false;
			l++; r--;
		}
		return true;
	}

	static long min(long a,long b,long c)
	{
		return Math.min(a, Math.min(c, b));
	}

	static void print(int a)
	{
		System.out.println("! "+a);
	}
	static int ask(int a,int b)
	{
		System.out.println("? "+a+" "+b);
		return i();
	}
	static int find(int a)
	{
		if(par[a]<0)return a;
		return par[a]=find(par[a]);
	}
	static void union(int a,int b)
	{
		a=find(a);
		b=find(b);
		if(a!=b)
		{
			par[a]+=par[b]; //transfers the size
			par[b]=a;       //changes the parent
		}
	}
	static void swap(char A[],int a,int b)
	{
		char ch=A[a];
		A[a]=A[b];
		A[b]=ch;
	}

	static void sort(long[] a) //check for long
	{
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	static void setGraph(int N)
	{
		g=new ArrayList[N+1];
		dp=new long[2][N+1];
		L=new long[N+1];
		R=new long[N+1];
		for(int i=0; i<=N; i++)
		{

			g[i]=new ArrayList<Integer>();
		}
	}

	static  long pow(long a,long b)
	{
		long mod=1000000007;
		long pow=1;
		long x=a;
		while(b!=0)
		{
			if((b&1)!=0)pow=(pow*x)%mod;
			x=(x*x)%mod;
			b/=2;
		}
		return pow;
	}
	static long toggleBits(long x)//one's complement || Toggle bits
	{
		int n=(int)(Math.floor(Math.log(x)/Math.log(2)))+1;

		return ((1<<n)-1)^x;
	}
	static int countBits(long a)
	{
		return (int)(Math.log(a)/Math.log(2)+1);
	}
	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	static boolean isPrime(long N)
	{
		if (N<=1)  return false; 
		if (N<=3)  return true; 
		if (N%2 == 0 || N%3 == 0) return false; 
		for (int i=5; i*i<=N; i=i+6) 
			if (N%i == 0 || N%(i+2) == 0) 
				return false; 
		return true; 
	}
	static long GCD(long a,long b) 
	{
		if(b==0)
		{
			return a;
		}
		else return GCD(b,a%b );
	}

	//Debugging Functions Starts

	static void print(char A[])
	{
		for(char c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(boolean A[])
	{
		for(boolean c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(int A[])
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();	
	}
	static void print(long A[])
	{
		for(long i:A)System.out.print(i+ " ");
		System.out.println();

	}
	static void print(ArrayList<Integer> A)
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();
	}

	//Debugging Functions END
	//----------------------
	//IO FUNCTIONS STARTS
	static HashMap<Integer,Integer> Hash(int A[])
	{
		HashMap<Integer,Integer> mp=new HashMap<>();
		for(int a:A)
		{
			int f=mp.getOrDefault(a,0)+1;
			mp.put(a, f);
		}
		return mp;
	}
	static int i()
	{
		return in.nextInt();
	}

	static long l()
	{
		return in.nextLong();
	}

	static int[] input(int N){
		int A[]=new int[N];
		for(int i=0; i<N; i++)
		{
			A[i]=in.nextInt();
		}
		return A;
	}

	static long[] inputLong(int N)     {
		long A[]=new long[N];
		for(int i=0; i<A.length; i++)A[i]=in.nextLong();
		return A;
	}

	//IO FUNCTIONS END

}

class node implements Comparable<node>
{
	int x,index; boolean right;
	node(int x,boolean right,int index)
	{
		this.x=x;
		this.right=right;
		this.index=index;
	}
	public int compareTo(node X)
	{
		return this.x-X.x;
	}
}

//Code For FastReader
//Code For FastReader
//Code For FastReader
//Code For FastReader
class FastReader
{
	BufferedReader br;
	StringTokenizer st;
	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	String next()
	{
		while(st==null || !st.hasMoreElements())
		{
			try
			{
				st=new StringTokenizer(br.readLine());
			}
			catch(IOException e)
			{
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt()
	{
		return Integer.parseInt(next());
	}

	long nextLong()
	{
		return Long.parseLong(next());
	}
	//gey
	double nextDouble()
	{
		return Double.parseDouble(next());
	}

	String nextLine()
	{
		String str="";
		try
		{
			str=br.readLine();
		}
		catch (IOException e)
		{
			e.printStackTrace();
		}
		return str;
	}

}