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
// package com.prituladima;

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public final class C {

    Range[] ranges;
    long[][] dp;
        ArrayList<Integer>[] adj;
    SparseTree tree;

    private void solve_() {
        int n = nextInt();
        ranges = new Range[n + 1];
        for (int i = 1; i < ranges.length; i++) {
            ranges[i] = new Range();
            ranges[i].l = nextInt();
            ranges[i].r = nextInt();
        }
        dp = new long[n + 20][2];
        tree = new SparseTree(n + 20, n + 20);
        adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 1; i < n; i++) {
            int u = nextInt(), v = nextInt();
            adj[u].add(v);
            adj[v].add(u);
            tree.add(u, v);
            tree.add(v, u);
        }

//        Tree tree = nextTree(n, false);
        int root = 1;

        dfsTree(root, -1);

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

    }

    private Tree nextTree(int amountOfVertexes, boolean isDirected) {
        Tree tree = new Tree();
        for (int i = 1; i <= amountOfVertexes; i++) {
            tree.put(i, new HashSet<>());
        }
        for (int i = 1; i <= amountOfVertexes - 1; i++) {
            int from = nextInt();
            int to = nextInt();
            tree.get(from).add(to);
            if (!isDirected) {
                tree.get(to).add(from);
            }
        }
        return tree;
    }


    private void dfsTree(int from, int parent) {
//        if (dp[from][0] != 0 || dp[from][1] != 0) {
//            throw new RuntimeException("dp[from][0] != 0 || dp[from][1] != 0");
//        }

        for (int to : adj[from]) {
//        for (int edgeIndex = tree.last[from]; edgeIndex != -1; edgeIndex = tree.prev[edgeIndex]) {
//            int to = tree.to[edgeIndex];
            if (parent != to) {
                dfsTree(to, from);

                dp[from][0] += Math.max(
                        Math.abs(ranges[from].l - ranges[to].l) + dp[to][0],
                        Math.abs(ranges[from].l - ranges[to].r) + dp[to][1]
                );
                dp[from][1] += Math.max(
                        Math.abs(ranges[from].r - ranges[to].l) + dp[to][0],
                        Math.abs(ranges[from].r - ranges[to].r) + dp[to][1]
                );
            }
        }

    }


    /**
     * Graphs
     */
    private static class Graph extends HashMap<Integer, Collection<Integer>> {

    }

    private static class Tree extends Graph {

    }

    private static class SparseTree {

        int edges;
        int[] last, prev, to;

        public SparseTree(int n, int edgeCapacity) {
            edges = 0;
            last = new int[2 * n];
            Arrays.fill(last, -1);
            prev = new int[2 * n];
            to = new int[2 * n];
        }

        /* add directed edge (x, y) */
        public void add(int x, int y) {
            prev[edges] = last[x];//            ne[idx] = h[a];
            last[x] = edges;//            h[a] = idx;
            to[edges] = y;//            e[idx] = b;
            edges += 1;
//            e[idx] = b;
//            ne[idx] = h[a];
//            h[a] = idx++;

//            prev[edgePointer] = last[a];
//            last[a] = edgePointer;
//            to[edgePointer] = b;
//            edgePointer++;
        }

        /* iterate over adjacent nodes of x */
//for(int e = last[x]; e != -1; e = prev[e])
//        {   int y = to[e];
//            /* process edge (x, y) */
//        }
    }

//    private static class Tree_Optimized /*extends Tree*/ {
//
//        boolean isDirected;
//        int capacity;
//        int[][] graph;
//        int[] adjListCapacities;
//
//
//        public Tree_Optimized() {
//            this(false);
//        }
//
//        public Tree_Optimized(boolean isDirected) {
//            this.isDirected = isDirected;
//            this.capacity = 16;
//            this.graph = new int[capacity][];
//            Arrays.fill(this.graph, new int[16].clone());
//            adjListCapacities = new int[capacity];
//            Arrays.fill(this.adjListCapacities, 16);
//        }
//
//        public void addEdge(int from, int to) {
//            ensureCapacity(graph, from, to);
//
//        }
//
//        private void ensureCapacity(int[][] graph, int from, int to) {
//            if (graph.length == from) {
//                int biggerCapacity = capacity + capacity >> 1;
//                int[][] biggerGraph = new int[biggerCapacity][];
//                System.arraycopy(graph, 0, biggerGraph, 0, graph.length);
//                for (int i = graph.length; i < biggerGraph.length; i++) {
//                    biggerGraph[i] = new int[16];
//                    adjListCapacities[i] = 16;
//                }
//                graph = biggerGraph;
//            }
//
//            if (graph[to].length == to) {
//                int biggerCapacity = adjListCapacities[to] + adjListCapacities[to] >> 1;
//                int[] biggerList = new int[biggerCapacity];
//                System.arraycopy(graph[to], 0, biggerList, 0, graph[to].length);
//
//                graph[to] = biggerList;
//            }
//        }
//
//
//    }

    private static class Edge {
        int from;
        int to;
    }

    private static class Range {
        int l;
        int r;
    }

    private void solve() {
        int t = nextInt();
        for (int i = 0; i < t; i++) {
            solve_();
        }
    }

    public static void main(String[] args) {
        new C().run();
    }

    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter writer;

    private void run() {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
             PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out))) {
            this.reader = reader;
            this.writer = writer;
            this.tokenizer = null;
            solve();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }


    private int nextInt(int radix) {
        return Integer.parseInt(nextToken(), radix);
    }

    private int nextInt() {
        return Integer.parseInt(nextToken());
    }

    private long nextLong(int radix) {
        return Long.parseLong(nextToken(), radix);
    }

    private long nextLong() {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() {
        return Double.parseDouble(nextToken());
    }

    private int[] nextArr(int size) {
        return Arrays.stream(new int[size]).map(c -> nextInt()).toArray();
    }

    private long[] nextArrL(int size) {
        return Arrays.stream(new long[size]).map(c -> nextLong()).toArray();
    }

    private double[] nextArrD(int size) {
        return Arrays.stream(new double[size]).map(c -> nextDouble()).toArray();
    }

    private char[][] nextCharMatrix(int n) {
        return IntStream.range(0, n).mapToObj(i -> nextToken().toCharArray()).toArray(char[][]::new);
    }

    private int[][] nextIntMatrix(final int n, final int m) {
        return IntStream.range(0, n).mapToObj(i -> nextArr(m)).toArray(int[][]::new);
    }

    private double[][] nextDoubleMatrix(final int n, final int m) {
        return IntStream.range(0, n).mapToObj(i -> nextArrD(m)).toArray(double[][]::new);
    }

    private String nextToken() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    private void printf(String format, Object... args) {
        writer.printf(format, args);
    }

    private void print(Object o) {
        writer.print(o);
    }

    private void println() {
        writer.println();
    }

    private void println(Object o) {
        print(o);
        println();
    }

    private void flush() {
        writer.flush();
    }

}