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
def point_type(point):
    # why not 
    return "even" if point[0]+point[1] % 2 == 0 else "odd"

def solve(n, lc, coordinates):
    """
    layout:
    (1, 1),
    (2, 1), (2, 2),
    (3, 1), (3, 2), (3, 3),
    (4, 1), (4, 2), (4, 3), (4, 4),
    (5, 1), (5, 2), (5, 3), (5, 4), (5, 5),
    (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6),
    ...

    (n, 1), (n, 2), ..., (n, n-1), (n, n) 

    down a column: even points and odd points alternate 

    moves:
    straight down 1 point if point_type == "even"
    else move down 1 right 1 
   
    i can follow a diagonal moving right and get 
    to any point along that diagonal which costs 0

    or i can go along the diagonal and go down whenever
    there's an even point 

    i've no idea how to do this properly, 
    but let's see what happens :)


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

    that means there's no path through a pair of points like (4, 1) and (5, 3) which is impossible to get to!
    """
    # start at (1, 1)
    current_point = (1, 1) 
    # start at coordinates[0]
    coordinates_index = 0 

    cost = 0

    # while we still have points to visit
    while coordinates_index < lc:
        # fetch next_point in the coordinates list
        next_point = coordinates[coordinates_index]

        # r_distance = left or right distance
        # c_distance = down (it's always move down)
        r_distance = current_point[0] - next_point[0] 
        c_distance = current_point[1] - next_point[1] 

        # i'll have 4 different options:
        # i) current_point == "even" and next_point == "even"
        # ii) current_point == "even" and next_point == "odd"

        # ii) current_point == "odd" and next_point == "odd"
        # iv) current_point == "odd" and next_point == "even"

        if point_type(current_point) == "even" and point_type(next_point) == "even":
            # i'll have to go down twice, 
            # which means i'll make a new activation path which costs +1
            # so for each "move down twice" i will get cost +1
            # so finally cost += c_distance / 2
            cost += c_distance // 2
        
        elif point_type(current_point) == "even" and point_type(next_point) == "odd":
            # we can always get from even to odd, no problem
            # cost += 0
            pass # skip this      

        elif point_type(current_point) == "odd" and point_type(next_point) == "odd":
            # similar to even-even 
            # if current_point and next_point are on the same diagonal:
            # cost += 0 (as mentioned above under moves)
            # same diagonal means abs(r_distance) = abs(c_distance)
            if abs(r_distance) == abs(c_distance):
                cost += 0 

            else:
                # else:
                # we can pass through an even point in between two odd points 
                # then we have an even number of rows between the two points
                # ie c_distance % 2 == 0

                if c_distance % 2 == 0:
                    cost += 0
                else:
                    # unfortunately we must (at some point) make an illegal move
                    # either to make the c_distance even or move over a point horizontally
                    # which again means that c_distance is even (otherwise we could've done that in the first place)
                    
                    # so, activate a new edge means cost +1
                    cost += 1

        elif point_type(current_point) == "odd" and point_type(next_point) == "even":  
            # the last case 
            # similar to the even-odd
            cost += 0     
        
        # exchange points
        current_point = next_point
        coordinates_index += 1

    # finally
    return cost

t = int(input())
for test in range(t):
    n = int(input()) 
    rs = [int(r) for r in input().split()]
    cs = [int(c) for c in input().split()]
    # (r, c)
    coordinates = []
    for i in range(0, n):
        coordinates.append((rs[i], cs[i]))
    
    # sort by r
    coordinates = sorted(coordinates, key=lambda x: x[0])
    lc = len(coordinates)
    print(solve(n, lc, coordinates))  