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.util.*;

public class TriangularPaths implements Runnable {

   void solve() throws IOException {
      int t = ri();
      while (t-- > 0) {

         int n = ri();

         int[][] arr = new int[n][2];
         for (int i = 0; i < n; i++) {
            arr[i][0] = ri();
         }
         for (int i = 0; i < n; i++) {
            arr[i][1] = ri();
         }

         shuffle(arr);

         Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));

         long res = 0;
         for (int i = 0; i < n; i++) {

            if (i == 0) {
               res += getCount(1, 1, arr[i][0], arr[i][1]);
            } else {
               res += getCount(arr[i - 1][0], arr[i - 1][1], arr[i][0], arr[i][1]);
            }
         }
         println(res);
      }
   }

   int getCount(int a, int b, int aa, int bb) {
      int ans = 0;

      if (aa - a == bb - b) {
         // Same area
         if ((a + b & 1) == 0) {
            ans += aa - a;
         }
      } else {

         // Traverse between different areas
         ans += (aa - bb) / 2 - (a - b) / 2;
      }
      return ans;
   }

   /************************************************************************************************************************************************/
   public static void main(String[] args) throws IOException {
      new Thread(null, new TriangularPaths(), "1").start();
   }

   static PrintWriter out = new PrintWriter(System.out);
   static Reader read = new Reader();
   static StringBuilder sbr = new StringBuilder();
   static int mod = (int) 1e9 + 7;
   static int dmax = Integer.MAX_VALUE;
   static long lmax = Long.MAX_VALUE;
   static int dmin = Integer.MIN_VALUE;
   static long lmin = Long.MIN_VALUE;

   @Override
   public void run() {
      try {
         solve();
         out.close();
      } catch (IOException e) {
         e.printStackTrace();
         System.exit(1);
      }
   }

   static class Reader {
      private byte[] buf = new byte[1024];
      private int index;
      private InputStream in;
      private int total;

      public Reader() {
         in = System.in;
      }

      public int scan() throws IOException {
         if (total < 0)
            throw new InputMismatchException();
         if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0)
               return -1;
         }
         return buf[index++];
      }

      public int intNext() throws IOException {
         int integer = 0;
         int n = scan();
         while (isWhiteSpace(n))
            n = scan();
         int neg = 1;
         if (n == '-') {
            neg = -1;
            n = scan();
         }
         while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
               integer *= 10;
               integer += n - '0';
               n = scan();
            } else
               throw new InputMismatchException();
         }
         return neg * integer;
      }

      public double doubleNext() throws IOException {
         double doub = 0;
         int n = scan();
         while (isWhiteSpace(n))
            n = scan();
         int neg = 1;
         if (n == '-') {
            neg = -1;
            n = scan();
         }
         while (!isWhiteSpace(n) && n != '.') {
            if (n >= '0' && n <= '9') {
               doub *= 10;
               doub += n - '0';
               n = scan();
            } else
               throw new InputMismatchException();
         }
         if (n == '.') {
            n = scan();
            double temp = 1;
            while (!isWhiteSpace(n)) {
               if (n >= '0' && n <= '9') {
                  temp /= 10;
                  doub += (n - '0') * temp;
                  n = scan();
               } else
                  throw new InputMismatchException();
            }
         }
         return doub * neg;
      }

      public String read() throws IOException {
         StringBuilder sb = new StringBuilder();
         int n = scan();
         while (isWhiteSpace(n))
            n = scan();
         while (!isWhiteSpace(n)) {
            sb.append((char) n);
            n = scan();
         }
         return sb.toString();
      }

      private boolean isWhiteSpace(int n) {
         if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
            return true;
         return false;
      }
   }

   static void shuffle(int[] aa) {
      int n = aa.length;
      Random rand = new Random();
      for (int i = 1; i < n; i++) {
         int j = rand.nextInt(i + 1);
         int tmp = aa[i];
         aa[i] = aa[j];
         aa[j] = tmp;
      }
   }

   static void shuffle(int[][] aa) {
      int n = aa.length;
      Random rand = new Random();
      for (int i = 1; i < n; i++) {
         int j = rand.nextInt(i + 1);
         int first = aa[i][0];
         int second = aa[i][1];
         aa[i][0] = aa[j][0];
         aa[i][1] = aa[j][1];
         aa[j][0] = first;
         aa[j][1] = second;
      }
   }

   static final class Comparators {
      public static final Comparator<int[]> pairIntArr = (x, y) -> x[0] == y[0] ? compare(x[1], y[1])
            : compare(x[0], y[0]);

      private static final int compare(final int x, final int y) {
         return Integer.compare(x, y);
      }
   }

   static void print(Object object) {
      out.print(object);
   }

   static void println(Object object) {
      out.println(object);
   }

   static int[] iArr(int len) {
      return new int[len];
   }

   static long[] lArr(int len) {
      return new long[len];
   }

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

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

   static long max(Long a, Long b) {
      return Math.max(a, b);
   }

   static int max(int a, int b) {
      return Math.max(a, b);
   }

   static int ri() throws IOException {
      return read.intNext();
   }

   static long rl() throws IOException {
      return Long.parseLong(read.read());
   }

   static String rs() throws IOException {
      return read.read();
   }

   static double rd() throws IOException {
      return read.doubleNext();
   }
}
