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.util.*;
import java.util.Map.Entry;
import java.io.*;
import java.lang.*;
//May CodeChef Starters 2021 Division 3 (Rated)
   public class Problem {
    static int Mod = 1000000007;
    static boolean visited[]=new boolean[15];
    static int dp[]=new int[15];
    public static void main(String[] args) {
        MyScanner scan = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        // int t=1;                  
        int t=scan.nextInt();
        while(t-->0){
             int n=scan.nextInt();
             ArrayList<Pair> list=new ArrayList<>();
             list.add(new Pair(0,0));
             for(int i=1;i<=n;i++){
                 list.add(new Pair(scan.nextLong(),scan.nextLong()));
             }
             ArrayList<Integer> adj[]=new ArrayList[n+1];
             for(int i=0;i<=n;i++)
             adj[i]=new ArrayList<>();

             for(int i=0;i<n-1;i++){
                 int a=scan.nextInt();
                 int b=scan.nextInt();
                 adj[a].add(b);
                 adj[b].add(a);
             }

             long dp[][]=new long[n+1][2];

             dfs(1,0,list,adj,dp);

             out.println(Math.max(dp[1][0],dp[1][1]));


       }
         out.close();
    }


    static void dfs(int i,int parent,ArrayList<Pair>list, ArrayList<Integer> adj[], long dp[][]){
                   
            for(int child : adj[i]){
                if(child==parent)
                continue;
                dfs(child,i,list,adj,dp);
                dp[i][0] +=  Math.max( Math.abs(list.get(i).l - list.get(child).l) + dp[child][0] , Math.abs(list.get(i).l - list.get(child).r) + dp[child][1] );
                dp[i][1] +=  Math.max( Math.abs(list.get(i).r - list.get(child).r) + dp[child][1] , Math.abs(list.get(i).r - list.get(child).l) + dp[child][0] );
            }

    }


    static class Pair {
        long l; long r;
        
        @Override
        public String toString() {
            return "Pair [l=" + l + ", r=" + r + "]";
        }

        Pair(long l, long r) {
            this.l = l; this.r = r;
        }
    }

    static boolean isPrime(int num){
        if(num<=1)
        return false;
  
      for (int i = 2; i <= Math.sqrt(num); ++i) {
        if (num % i == 0) {
            return false;
        }
      }
      return true;
    }
 
    public static void sort(int[] array) {
        ArrayList<Integer> copy = new ArrayList<>();
        for (Integer i : array)
            copy.add(i);
        Collections.sort(copy);
        for (int i = 0; i < array.length; i++)
            array[i] = copy.get(i);
    }

    public static void sort(long[] array) {
        ArrayList<Long> copy = new ArrayList<>();
        for (Long i : array)
            copy.add(i);
        Collections.sort(copy);
        for (int i = 0; i < array.length; i++)
            array[i] = copy.get(i);
    }

    static int countDigit(int n)
    {
        int count = 0;
        while (n != 0) {
            n = n / 10;
            ++count;
        }
        return count;
    }

    public static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b); // gcd(a,b) = gcd(a-b,b) or gcd(a,b) = gcd(b,a%b) where a>b
    }

   public static long lcm(long a, long b){
       return (a / gcd(a, b)) * b;
   }

    // recursive code  O(log(Y))
    static long pow(long x, long y) { 
        long temp;
        if (y == 0) // a^b= (a^b/2)^2 if b is even
            return 1; // = (a*a^(b-1)) if b is odd
        temp = pow(x, y / 2);               // storing and then using
        if (y % 2 == 0)
            return temp * temp;
        else
            return x * temp * temp;
    }

    //iterative code  O(log(Y))
    static long pow(long x, long y, int p)
    {
      long res = 1; // Initialize result
      x = x % p; // Update x if it is more than or equal to p
   
      if (x == 0)
        return 0; // In case x is divisible by p;
   
      while (y > 0)
      {
        // If y is odd, multiply x with result
        if ((y & 1) != 0)
          res = (res * x) % p;
   
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
      }
      return res;
    }

    static long mod(long x) {
        return ((x % Mod + Mod) % Mod);
    }

    static long add(long a, long b) {
        return mod(mod(a) + mod(b));
    }

    static long mul(long a, long b) {
        return mod(mod(a) * mod(b));
    }
  

}

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        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());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

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

}
