Consider an infinite triangle made up of layers. Let's number the layers, starting from one, from the top of the triangle (from top to bottom). The k-th layer of the triangle contains k points, numbered from left to right. Each point of an infinite triangle is described by a pair of numbers (r, c) (1 ≤ c ≤ r), where r is the number of the layer, and c is the number of the point in the layer. From each point (r, c) there are two directed edges to the points (r+1, c) and (r+1, c+1), but only one of the edges is activated. If r + c is even, then the edge to the point (r+1, c) is activated, otherwise the edge to the point (r+1, c+1) is activated. Look at the picture for a better understanding.

<image> Activated edges are colored in black. Non-activated edges are colored in gray.

From the point (r_1, c_1) it is possible to reach the point (r_2, c_2), if there is a path between them only from activated edges. For example, in the picture above, there is a path from (1, 1) to (3, 2), but there is no path from (2, 1) to (1, 1).

Initially, you are at the point (1, 1). For each turn, you can: 

  * Replace activated edge for point (r, c). That is if the edge to the point (r+1, c) is activated, then instead of it, the edge to the point (r+1, c+1) becomes activated, otherwise if the edge to the point (r+1, c+1), then instead if it, the edge to the point (r+1, c) becomes activated. This action increases the cost of the path by 1; 
  * Move from the current point to another by following the activated edge. This action does not increase the cost of the path. 



You are given a sequence of n points of an infinite triangle (r_1, c_1), (r_2, c_2), …, (r_n, c_n). Find the minimum cost path from (1, 1), passing through all n points in arbitrary order.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) is the number of test cases. Then t test cases follow.

Each test case begins with a line containing one integer n (1 ≤ n ≤ 2 ⋅ 10^5) is the number of points to visit.

The second line contains n numbers r_1, r_2, …, r_n (1 ≤ r_i ≤ 10^9), where r_i is the number of the layer in which i-th point is located.

The third line contains n numbers c_1, c_2, …, c_n (1 ≤ c_i ≤ r_i), where c_i is the number of the i-th point in the r_i layer.

It is guaranteed that all n points are distinct.

It is guaranteed that there is always at least one way to traverse all n points.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output the minimum cost of a path passing through all points in the corresponding test case.

Example

Input


4
3
1 4 2
1 3 1
2
2 4
2 3
2
1 1000000000
1 1000000000
4
3 10 5 8
2 5 2 4


Output


0
1
999999999
2

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;


// graph, dfs,bfs, get connected components,iscycle, isbipartite, dfs on trees



public class scratch_25{
    static class Graph{

        public static class Vertex{
            HashMap<Integer,Integer> nb= new HashMap<>();     // for neighbours of each vertex
        }

        public static HashMap<Integer,Vertex> vt;   // for vertices(all)

        public Graph(){
            vt= new HashMap<>();
        }

        public static int numVer(){
            return vt.size();
        }

        public static boolean contVer(int ver){
            return vt.containsKey(ver);
        }

        public static void addVer(int ver){
            Vertex v= new Vertex();
            vt.put(ver,v);
        }






        public static void addEdge(int ver1, int ver2, int weight){
            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }
            Vertex v1= vt.get(ver1);
            Vertex v2= vt.get(ver2);
            v1.nb.put(ver2,weight);                                 // if previously there is an edge, then this replaces that edge
            v2.nb.put(ver1,weight);
        }

        public static void delEdge(int ver1, int ver2){

            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }
            vt.get(ver1).nb.remove(ver2);
            vt.get(ver2).nb.remove(ver1);
        }
        public static void delVer(int ver){
            if(!vt.containsKey(ver)){
                return;
            }
            Vertex v1= vt.get(ver);
            ArrayList<Integer> arr= new ArrayList<>(v1.nb.keySet());
            for (int i = 0; i <arr.size() ; i++) {
                int s= arr.get(i);
                vt.get(s).nb.remove(ver);
            }
            vt.remove(ver);
        }
        static boolean done[];
        static int parent[];
        static ArrayList<Integer>vals= new ArrayList<>();


        public static boolean isCycle(int i){
            Stack<Integer>stk= new Stack<>();

            stk.push(i);
            while(!stk.isEmpty()){
                int x= stk.pop();
                vals.add(x);
                //   System.out.print("current="+x+" stackinit="+stk);
                if(!done[x]){
                    done[x]=true;
                }
                else if(done[x] ){
                    return true;
                }

                ArrayList<Integer>ar= new ArrayList<>(vt.get(x).nb.keySet());
                for (int j = 0; j <ar.size() ; j++) {
                    if(parent[x]!=ar.get(j)){
                        parent[ar.get(j)]=x;
                        stk.push(ar.get(j));
                    }
                }
                // System.out.println(" stackfin="+stk);
            }
            return false;
        }
        static int[]level;
        static int[] curr;
        static int[] fin;

        public static void dfs(int src){
            done[src]=true;
            level[src]=0;
            Queue<Integer>q= new LinkedList<>();
            q.add(src);
            while(!q.isEmpty()){
                int x= q.poll();
                ArrayList<Integer>arr= new ArrayList<>(vt.get(x).nb.keySet());
                for (int i = 0; i <arr.size() ; i++) {
                    int v= arr.get(i);
                    if(!done[v]){
                        level[v]=level[x]+1;
                        done[v]=true;
                        q.offer(v);
                    }
                }
            }
        }
        static int oc[];
        static int ec[];


        public static void dfs1(int src){
            Queue<Integer>q= new LinkedList<>();
            q.add(src);
            done[src]= true;
            //    int count=0;
            while(!q.isEmpty()){

                int x= q.poll();
                //   System.out.println("x="+x);
                int even= ec[x];
                int odd= oc[x];
                if(level[x]%2==0){
                    int val= (curr[x]+even)%2;
                    if(val!=fin[x]){
                        //  System.out.println("bc");
                        even++;
                        vals.add(x);
                    }
                }
                else{
                    int val= (curr[x]+odd)%2;
                    if(val!=fin[x]){
                        //   System.out.println("bc");
                        odd++;
                        vals.add(x);
                    }

                }
                ArrayList<Integer>arr= new ArrayList<>(vt.get(x).nb.keySet());
                //   System.out.println(arr);
                for (int i = 0; i <arr.size() ; i++) {
                    int v= arr.get(i);
                    if(!done[v]){
                        done[v]=true;
                        oc[v]=odd;
                        ec[v]=even;
                        q.add(v);
                    }
                }
            }

        }

        static long popu[];
        static long happy[];
        static long count[]; // total people crossing that pos
        static long sum[]; // total sum of happy people including that.


        public static void bfs(int x){
            done[x]=true;
            long total= popu[x];
//            long smile= happy[x];
            ArrayList<Integer>nbrs= new ArrayList<>(vt.get(x).nb.keySet());
            for (int i = 0; i <nbrs.size() ; i++) {
                int r= nbrs.get(i);
                if(!done[r]){
                    bfs(r);
                    total+=count[r];
//                    smile+=sum[r];
                }
            }
            count[x]=total;
//            sum[x]=smile;
        }


        public static void bfs1(int x){
            done[x]=true;
//            long total= popu[x];
            long smile= 0;
            ArrayList<Integer>nbrs= new ArrayList<>(vt.get(x).nb.keySet());
            for (int i = 0; i <nbrs.size() ; i++) {
                int r= nbrs.get(i);
                if(!done[r]){
                    bfs1(r);
//                    total+=count[r];
                    smile+=happy[r];
                }
            }
//            count[x]=total;
            sum[x]=smile;
        }


    }




    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /**
         * call this method to initialize reader for InputStream
         */
        static void init(InputStream input) {
            reader = new BufferedReader(
                    new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /**
         * get next word
         */
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer(
                        reader.readLine());
            }
            return tokenizer.nextToken();
        }

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

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

        static long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }


    static class Pair implements Comparable<Pair>     {
        int x;
        int val;



        public Pair(int x, int val) {
            this.x = x;
            this.val = val;


        }


        @Override
        public String toString() {
            return x + " " + val;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.x >o.x){
                return 1;
            }
            else if(this.x==o.x){
                return 0;
            }
            else{
                return -1;
            }
        }


    }



    static class Node implements Comparable<Node>{
        int ind;
        int len;
        int val;
        Node prev;
        Node next;
        public Node(int ind, int len,int val){
            this.ind=ind;
            this.len=len;
            this.val=val;
        }

        @Override
        public String toString() {
            if(this.next!=null){
            return ind+ " " + len+" "+val+" "+this.next.val;
        }
            return ind+" "+len+" "+val+" "+-1;


        }

        @Override
        public int compareTo(Node o) {
            if(this.len <o.len){
                return 1;
            }
            if(this.ind==o.ind && this.len==o.len && this.val==o.val){
                return 0;
            }
             if(this.len==o.len){
                if(this.ind>o.ind){
                    return 1;
                }
                else{
                    return -1;
                }
            }
            return -1;

        }
        @Override
        public boolean equals(Object x){
            Node a= (Node)x;
            if(this.ind==a.ind && this.len==a.len && this.val==a.val){
                return true;
            }
            return false;
        }
    }


    // After writing solution, quick scan for:
    //   array out of bounds
    //   special cases e.g. n=1?
    //
    // Big numbers arithmetic bugs:
    //   int overflow
    //   sorting, or taking max, or negative after MOD

    static String remove(String s)
    {

        // Stores the frequency of characters
        int[] count = new int[26];

        // Mark visited characters
        int[] visited = new int[26];

        int n = s.length();


        // Stores count of each character
        for(int i = 0; i < n; i++)
            count[s.charAt(i) - 'a']++;

        // Stores the resultant string
        String result = "";

        for(int i = 0; i < n; i++)

        {

            // Decrease the count of
            // current character
            count[s.charAt(i) - 'a']--;


            // If character is not already
            // in answer
            if (visited[s.charAt(i) - 'a'] == 0)
            {

                // Last character > S[i]
                // and its count > 0
                int size = result.length();
                while (size > 0 &&
                        result.charAt(size - 1) < s.charAt(i) &&
                        count[result.charAt(size - 1) - 'a'] > 0)
                {

                    // Mark letter unvisited
                    visited[result.charAt(size - 1) - 'a'] = 0;
                    result = result.substring(0, size - 1);
                    size--;
                }

                // Add s[i] in res and
                // mark it visited
                result += s.charAt(i);
                visited[s.charAt(i) - 'a'] = 1;
            }
        }

        // Return the resultant string
        return result;
    }


//static long dp[][];
    public static void main(String[] args)  throws IOException {
        Reader.init(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
       int t= Reader.nextInt();
        for (int tt = 0; tt <t ; tt++) {
            int n= Reader.nextInt();
            int a[][]= new int[n][2];
            for (int i = 0; i <n ; i++) {
                a[i][0]= Reader.nextInt();
            }
            for (int i = 0; i <n ; i++) {
                a[i][1]= Reader.nextInt();
            }
            ArrayList<Pair>x= new ArrayList<>();
            for (int i = 0; i <n ; i++) {
                x.add(new Pair(a[i][0],a[i][1]));
            }
            Collections.sort(x);
//            System.out.println(x);
            int ans=0;
            int cx=1;
            int cy=1;
            for (int i = 0; i <n ; i++) {
                int x1= x.get(i).val;
                int y1= x.get(i).x;

                if((cx+cy)%2==0){
                    if((x1-cx)==(y1-cy)){
                        ans+=(x1-cx);
                    }

                    else if((x1-cx-1)==(y1-cy)){
                        ans+=0;
                    }

                    else{
                        int g= cy+1+(x1-cx);

                        ans+=ceil_div(y1-g,2);
                    }
                }

                else{

                     if((x1-cx)==(y1-cy)){
                        ans+=0;
                    }

                    else{
                        int g= cy+(x1-cx);

                        ans+=ceil_div(y1-g,2);

                    }

                }
//                System.out.println("ans= "+ans+" cx= "+cx+" cy= "+cy+" x1= "+x1+" y1= "+y1);





                cx=x1;
                cy=y1;

            }







                out.append(ans+"\n");


















        }

        out.flush();
        out.close();
    }




    public static int localMinUtil(int[] arr, int low,
                                   int high, int n)
    {


        // Find index of middle element
        int mid = low + (high - low) / 2;

        // Compare middle element with its neighbours
        // (if neighbours exist)
        if(mid == 0 || arr[mid - 1] > arr[mid] && mid == n - 1 ||
                arr[mid] < arr[mid + 1])
            return mid;

            // If middle element is not minima and its left
            // neighbour is smaller than it, then left half
            // must have a local minima.
        else if(mid > 0 && arr[mid - 1] < arr[mid])
            return localMinUtil(arr, low, mid - 1, n);

        // If middle element is not minima and its right
        // neighbour is smaller than it, then right half
        // must have a local minima.
        return localMinUtil(arr, mid + 1, high, n);
    }

    // A wrapper over recursive function localMinUtil()
    public static int localMin(int[] arr, int n)
    {
        return localMinUtil(arr, 0, n - 1, n);
    }








    public static String convert(String s,int n){
        if(s.length()==n){
            return s;
        }
        else{
            int x= s.length();
            int v=n-x;
            String str="";
            StringBuilder s2= new StringBuilder();
            for (int i = 0; i <v ; i++) {
                s2.append('0');
            }
            StringBuilder s1= new StringBuilder(s);
            s2.append(s1);

//            str+=s;
            String q= s2.toString();
            return q;

        }
    }
    public static int lower(int arr[],int key){
        int low = 0;
        int high = arr.length-1;
        while(low < high){
            int mid = low + (high - low)/2;
            if(arr[mid] >= key){
                high = mid;
            }
            else{
                low = mid+1;
            }
        }
        return low;
    }

    public static int upper(int arr[],int key){
        int low = 0;
        int high = arr.length-1;
        while(low < high){
            int mid = low + (high - low+1)/2;
            if(arr[mid] <= key){
                low = mid;
            }
            else{
                high = mid-1;
            }
        }
        return low;
    }





    static long modExp(long a, long b, long mod) {
        //System.out.println("a is " + a + " and b is " + b);
        if (a==1) return 1;
        long ans = 1;
        while (b!=0) {
            if (b%2==1) {
                ans = (ans*a)%mod;
            }
            a = (a*a)%mod;
            b/=2;
        }
        return ans;
    }


    public static long modmul(long a, long b, long mod) {
        return b == 0 ? 0 : ((modmul(a, b >> 1, mod) << 1) % mod + a * (b & 1)) % mod;
    }

    static long sum(long n){
        //   System.out.println("lol="+ (n*(n-1))/2);
        return (n*(n+1))/2;
    }






    public static ArrayList<Integer> Sieve(int n) {
        boolean arr[]= new boolean [n+1];
        Arrays.fill(arr,true);
        arr[0]=false;
        arr[1]=false;
        for (int i = 2; i*i <=n ; i++) {
            if(arr[i]){
                for (int j = 2; j <=n/i ; j++) {
                    int u= i*j;
                    arr[u]=false;
                }}
        }
        ArrayList<Integer> ans= new ArrayList<>();
        for (int i = 0; i <n+1 ; i++) {
            if(arr[i]){
                ans.add(i);
            }
        }
        return ans;
    }




    static long power( long x, long y, long p)
    {

        long res = 1;


        x = x % p;

        if (x == 0) return 0;

        while (y > 0)
        {

            if((y & 1)==1)
                res = (res * x) % p;


            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static long ceil_div(long a, long b){
        return (a+b-1)/b;
    }

    static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

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

}