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
# cook your dish here
from collections import defaultdict,OrderedDict,Counter
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
# import numpy as np
from queue import Queue,PriorityQueue
from heapq import *
from statistics import *
from math import *
import fractions
import copy
from copy import deepcopy
import sys
import io
sys.setrecursionlimit(10000)
import math
import os
import bisect
import collections
mod=pow(10,9)+7
import random
from random import *
from time import  time;
def ncr(n, r, p=mod):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
            p - 2, p)) % p
def normalncr(n,r):
    r=min(r,n-r)
    count=1;
    for i in range(n-r,n+1):
        count*=i;

    for i in range(1,r+1):
        count//=i;
    return count

inf=float("inf")
adj=defaultdict(set)
visited=defaultdict(int)
def addedge(a,b):
    adj[a].add(b)
    adj[b].add(a)
def bfs(v):
    q=Queue()
    q.put(v)
    visited[v]=1
    while q.qsize()>0:
        s=q.get_nowait()
        print(s)
        for i in adj[s]:
            if visited[i]==0:
                q.put(i)
                visited[i]=1
def dfs(v,visited):
    if visited[v]==1:
        return;
    visited[v]=1

    print(v)
    for i in adj[v]:
        dfs(i,visited)
# a9=pow(10,6)+10
# prime = [True for i in range(a9 + 1)]
# def SieveOfEratosthenes(n):
#     p = 2
#     while (p * p <= n):
#         if (prime[p] == True):
#             for i in range(p * p, n + 1, p):
#                 prime[i] = False
#         p += 1
# SieveOfEratosthenes(a9)
# prime_number=[]
# for i in range(2,a9):
#     if prime[i]:
#         prime_number.append(i)
def reverse_bisect_right(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid+1
    return lo
def reverse_bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x >= a[mid]:
            hi = mid
        else:
            lo = mid+1
    return lo

def get_list():
    return list(map(int,input().split()))
def get_str_list_in_int():
    return [int(i) for i in list(input())]
def get_str_list():
    return list(input())
def get_map():
    return map(int,input().split())
def input_int():
    return int(input())
def matrix(a,b):
    return [[0 for i in range(b)] for j in range(a)]
def swap(a,b):
    return b,a
def find_gcd(l):
    a=l[0]
    for i in range(len(l)):
        a=gcd(a,l[i])
    return a;
def is_prime(n):
    sqrta=int(sqrt(n))
    for i in range(2,sqrta+1):
        if n%i==0:
            return 0;
    return 1;
def prime_factors(n):
    while n % 2 == 0:
        return [2]+prime_factors(n//2)
    sqrta = int(sqrt(n))


    for i in range(3,sqrta+1,2):
        if n%i==0:
            return [i]+prime_factors(n//i)

    return [n]
def p(a):
    if type(a)==str:
        print(a+"\n")
    else:
        print(str(a)+"\n")
def ps(a):
    if type(a)==str:
        print(a)
    else:
        print(str(a))
def kth_no_not_div_by_n(n,k):
    return k+(k-1)//(n-1)
def forward_array(l):
    n=len(l)
    stack = []
    forward=[0]*n
    for i in range(len(l) - 1, -1, -1):
        while len(stack) and l[stack[-1]] < l[i]:
            stack.pop()
        if len(stack) == 0:
            forward[i] = len(l);
        else:
            forward[i] = stack[-1]
        stack.append(i)
    return forward;
def backward_array(l):
    n=len(l)
    stack = []
    backward=[0]*n
    for i in range(len(l)):
        while len(stack) and l[stack[-1]] < l[i]:
            stack.pop()
        if len(stack) == 0:
            backward[i] = -1;
        else:
            backward[i] = stack[-1]
        stack.append(i)
    return backward
nc="NO"
yc="YES"
ns="No"
ys="Yes"

# import math as mt
# MAXN=10**7
# spf = [0 for i in range(MAXN)]
# def sieve():
#     spf[1] = 1
#     for i in range(2, MAXN):
#         # marking smallest prime factor
#         # for every number to be itself.
#         spf[i] = i
#
#         # separately marking spf for
#     # every even number as 2
#     for i in range(4, MAXN, 2):
#         spf[i] = 2
#
#     for i in range(3, mt.ceil(mt.sqrt(MAXN))):
#
#         # checking if i is prime
#         if (spf[i] == i):
#
#             # marking SPF for all numbers
#             # divisible by i
#             for j in range(i * i, MAXN, i):
#
#                 # marking spf[j] if it is
#                 # not previously marked
#                 if (spf[j] == j):
#                     spf[j] = i
# def getFactorization(x):
#     ret = list()
#     while (x != 1):
#         ret.append(spf[x])
#         x = x // spf[x]
#
#     return ret
# sieve()






# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
# input=stdin.readline
# print=stdout.write

def add(m,theta):
    counter=0
    res=[i for i in m]
    for i in range(len(m)):
        if m[i]==0:
            res[i]=theta[counter]
            counter+=1

    return res;

t=int(input())
for i in range(t):
    n=int(input())
    a=get_list()
    b=get_list()
    l=[[a[i],b[i]] for i in range(n)]
    l.sort()
    curr_r=1;
    curr_c=1;
    curr_diff=0;
    cost=0
    for i in range(n):
        a,b=l[i]
        diff=a-b;
        # print(diff,curr_diff)
        if diff==curr_diff:
            if (curr_r + curr_c) % 2 == 0:
                cost += abs(a-curr_r)
            else:
                pass

        else:
            if (curr_r+curr_c)%2==0:
                cost+=abs(diff-curr_diff)//2
            else:
                cost+=ceil(abs(diff-curr_diff)/2)
        curr_r=a;
        curr_c=b;
        curr_diff=diff
    print(cost)






