You are given two arrays of integers a_1, a_2, …, a_n and b_1, b_2, …, b_m.

You need to insert all elements of b into a in an arbitrary way. As a result you will get an array c_1, c_2, …, c_{n+m} of size n + m.

Note that you are not allowed to change the order of elements in a, while you can insert elements of b at arbitrary positions. They can be inserted at the beginning, between any elements of a, or at the end. Moreover, elements of b can appear in the resulting array in any order.

What is the minimum possible number of inversions in the resulting array c? Recall that an inversion is a pair of indices (i, j) such that i < j and c_i > c_j.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4). Description of the test cases follows.

The first line of each test case contains two integers n and m (1 ≤ n, m ≤ 10^6).

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

The third line of each test case contains m integers b_1, b_2, …, b_m (1 ≤ b_i ≤ 10^9).

It is guaranteed that the sum of n for all tests cases in one input doesn't exceed 10^6. The sum of m for all tests cases doesn't exceed 10^6 as well.

Output

For each test case, print one integer — the minimum possible number of inversions in the resulting array c.

Example

Input


3
3 4
1 2 3
4 3 2 1
3 3
3 2 1
1 2 3
5 4
1 3 5 3 1
4 3 6 1


Output


0
4
6

Note

Below is given the solution to get the optimal answer for each of the example test cases (elements of a are underscored).

  * In the first test case, c = [\underline{1}, 1, \underline{2}, 2, \underline{3}, 3, 4]. 
  * In the second test case, c = [1, 2, \underline{3}, \underline{2}, \underline{1}, 3]. 
  * In the third test case, c = [\underline{1}, 1, 3, \underline{3}, \underline{5}, \underline{3}, \underline{1}, 4, 6]. 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define SZ(x) (int)(x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int maxn = 4e6 + 6;
const int  inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 2e3 + 3;
ll qpow(ll x,ll y) { ll ans=1;x%=mod;  while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod;  y>>=1; } return ans; }
//
int _;


int n,m,k;
int a[maxn],b[maxn],c[maxn];
int d[maxn];
int cntb[maxn];
void upd(int x,int v) {
   for(;x<=k;x+=x&(-x)) d[x]+=v; 
}
int ask(int x) {
    int ans=0;
    for(;x>0;x-=x&(-x)) ans+=d[x];
    return ans;
}
vector<int>v[maxn];

#define ls rt<<1
#define rs rt<<1|1
#define mid (l+r>>1)

struct Node {
    int sm,ms;
}t[maxn*2];

void pu(int rt) {
    t[rt].sm=t[ls].sm+t[rs].sm;
    t[rt].ms=min({0,t[ls].ms,t[ls].sm+t[rs].ms});
}
void build(int rt,int l,int r) {
    t[rt].sm=1;t[rt].ms=0;
    if(l==r) {
        return ;
    } else {
        build(ls,l,mid);
        build(rs,mid+1,r);
        pu(rt);
    }
}
void change(int rt,int l,int r,int p,int v) {
    if(l==r) {
        t[rt].sm=v;t[rt].ms=min(v,0);
    }
    else {
        if(p<=mid) change(ls,l,mid,p,v);
        else change(rs,mid+1,r,p,v);
        pu(rt);
    }
}

#undef ls
#undef rs
#undef mid
void so() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),c[i]=a[i];
    for(int i=1;i<=m;i++) scanf("%d",&b[i]),c[i+n]=b[i];
    sort(c+1,c+1+2*n);
    k=unique(c+1,c+1+2*n)-c-1;
    for(int i=1;i<=k;i++) d[i]=cntb[i]=0,v[i].clear();
    ll ans=0;
    for(int i=1;i<=n;i++) {
        a[i]=lower_bound(c+1,c+1+k,a[i])-c;
        upd(a[i],1);
        ans+=i-ask(a[i]);
        v[a[i]].pb(i);
    }
    for(int i=1;i<=m;i++) {
        b[i]=lower_bound(c+1,c+1+k,b[i])-c;
        cntb[b[i]]++;
    }
    build(1,1,k);
    int les=0;
    for(int i=1;i<=k;i++) {
        for(auto j:v[i]) change(1,1,k,j,0);
        ans+=1ll*cntb[i]*(les+t[1].ms);
        les+=SZ(v[i]);
        for(auto j:v[i]) change(1,1,k,j,-1);
    }
    printf("%lld\n",ans);
}
void init() {


}  
int main() {
    init();
    for(scanf("%d",&_);_;_--) { 
        so();
    }
    return 0;
}