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
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int                long long // __int128 for big integers with c++ 17 (64)
#define double             long double
#define pb                 push_back
#define mp                 make_pair
#define vi                 vector<int>
#define vvi                vector<vector<int>>
#define vpii               vector<pair<int,int>>
#define pii                pair<int,int>
#define umap               unordered_map
#define all(c)             c.begin(),c.end()
#define si(c)              (int)c.size()
#define lb                 lower_bound
#define ub                 upper_bound
#define gi                 greater<int>
#define rev                reverse
#define ff                 first
#define ss                 second
#define yes                cout << "YES" << endl
#define no                 cout << "NO" << endl
#define ayes               cout << "Yes" << endl
#define ano                cout << "No" << endl
#define nl                 cout << endl
#define hello              cerr << "hello" << endl
#define sp(x)              fixed << setprecision(x)
#define re                 return
#define p_q                priority_queue
#define FAST               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;
//find_by_order(k)  --> value at kth index (iterator)
//order_of_key(k)   --> index of value k

void dbg_out(){cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
//copied from neal wu (The Legend)

const double pi = 3.14159265359;
const int mod = 1000000007;
const int modc = 998244353;
const int inf = LLONG_MAX;
const int neg_inf = LLONG_MIN;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //use rng() instead of rand() //shuffle(all(a),rng)

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int lcm(int a, int b)
{
    int g = __gcd(a,b);
    return (a*b)/g;
}

int inline power(int a, int b, int p){
    a %= p;
    int ans = 1;
    while(b>0){
        if(b & 1)
            ans = (ans*a)%p;
        a = (a*a)%p;
        b >>= 1;
    }
    return ans;
}

int mod_inv(int n, int p){
    return power(n,p-2, p);
}

bool inline isPrime(int n) {
    if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
    return true;
}

template<typename... T>
void W(T&&... args)
{
	((cout << sp(17) <<  args << " "), ...);
	nl;
}
template<typename... T>
void R(T&&... args)
{
	((cin >> args), ...);
}

template<class T>
void wv(T &v)
{
	for(auto x : v)
		cout << x << " " ;
	nl;
}
template<class T>
void rv(T &v)
{
	for(int i=0;i<si(v);i++)
		cin >> v[i];
}

int dx[] = {1,0,-1,0,1,-1,1,-1};  //for BFS in matrix
int dy[] = {0,1,0,-1,1,1,-1,-1};  //yeah! same

const int M = 3e5 + 5;

/*
int fact[M];
int ncr(int n, int r)
{
	int ans = fact[n];
	int denom = (fact[r]*fact[n-r])%mod;
	ans = (ans * mod_inv(denom,mod))%mod;
	return ans;
}
*/
//vector<int>v[M];

void solve()
{
	int i,j,sum = 0,prod = 1,maxl = neg_inf, minl = inf;
	int n;
	cin >> n;
	vpii v(n);
	for(int i = 0 ; i < n ;i++)
		cin >> v[i].ff;
	for(int i = 0 ; i < n ; i++)
		cin >> v[i].ss;
	sort(all(v));
	pii prev = {1,1};
	int cost = 0;
	for(auto x : v)
	{
		if(x == prev)
			continue;
		int right = x.ss - prev.ss;
		int total = x.ff - prev.ff;
		int left = total - right;

		if(prev.ff == prev.ss && x.ff == x.ss)
		{
			cost += x.ff - prev.ff;
			continue;
		}

		if((prev.ff + prev.ss)%2)
			cost += (left + 1)/2;
		else
		{
			if(left % 2)
				cost += left/2;
			else
				cost += left/2 + 1;
		}
		prev = x;
	}
	cout << cost << endl;
}
int32_t main()
{
	FAST;
	int t = 1;
	cin >> t;
	/*
	fact[0] = 1;
	for(int i = 1;i<M;i++)
		fact[i] = (i * fact[i-1])%mod;
		*/
	int test = 1;
	while(t--)
	{
	//	cout << "Case #" << test << ": ";
		solve();
		test++;
	}
} 
