#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, n, m, a[N], b[N], st[N << 1], top;
vector<int> head[N << 1];
map<int, int> M;
struct Bit {
  int tr[N << 1], lim;
  void modify(int x, int y) {
    for (; x <= lim; x += x & -x) tr[x] += y;
  }
  int query(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += tr[x];
    return ret;
  }
} B;
struct Seg {
  int tag, Min;
} tr[N << 2];
void upd(int p) { tr[p].Min = min(tr[p << 1].Min, tr[p << 1 | 1].Min); }
void build(int p, int l, int r) {
  tr[p].tag = 0;
  if (l == r) {
    tr[p].Min = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  upd(p);
}
void f(int p, int k) {
  tr[p].Min += k;
  tr[p].tag += k;
}
void pushdown(int p, int l, int r) {
  int mid = (l + r) >> 1;
  if (tr[p].tag) {
    f(p << 1, tr[p].tag);
    f(p << 1 | 1, tr[p].tag);
    tr[p].tag = 0;
  }
}
void modify(int p, int l, int r, int nl, int nr, int k) {
  if (l == nl && r == nr) {
    f(p, k);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(p, l, r);
  if (nr <= mid)
    modify(p << 1, l, mid, nl, nr, k);
  else if (nl > mid)
    modify(p << 1 | 1, mid + 1, r, nl, nr, k);
  else
    modify(p << 1, l, mid, nl, mid, k),
        modify(p << 1 | 1, mid + 1, r, mid + 1, nr, k);
  upd(p);
}
int main() {
  ios::sync_with_stdio(0);
  cin >> T;
  while (T--) {
    cin >> n >> m;
    top = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i], st[++top] = a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i], st[++top] = b[i];
    sort(b + 1, b + 1 + m);
    sort(st + 1, st + 1 + top);
    int num = unique(st + 1, st + 1 + top) - st - 1;
    for (int i = 1; i <= num; ++i) M[st[i]] = i;
    for (int i = 1; i <= n; ++i) a[i] = M[a[i]];
    for (int i = 1; i <= m; ++i) b[i] = M[b[i]];
    B.lim = num;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans += B.query(num) - B.query(a[i]);
      B.modify(a[i], 1);
    }
    build(1, 1, n);
    for (int i = 1; i <= n; ++i) head[a[i]].push_back(i);
    int now = 0;
    for (int i = 1; i <= m; ++i) {
      while (now < b[i]) {
        for (int i = 0; i < head[now].size(); ++i)
          modify(1, 1, n, head[now][i], n, -1);
        ++now;
        for (int i = 0; i < head[now].size(); ++i)
          modify(1, 1, n, head[now][i], n, -1);
      }
      int tmp = B.query(b[i] - 1);
      ans += B.query(b[i] - 1);
      int Min = min(tr[1].Min, 0);
      ans += Min;
    }
    cout << ans << endl;
    for (int i = 0; i <= num; ++i) head[i].clear(), B.tr[i] = 0;
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

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]. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, n, m, a[N], b[N], st[N << 1], top;
vector<int> head[N << 1];
map<int, int> M;
struct Bit {
  int tr[N << 1], lim;
  void modify(int x, int y) {
    for (; x <= lim; x += x & -x) tr[x] += y;
  }
  int query(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += tr[x];
    return ret;
  }
} B;
struct Seg {
  int tag, Min;
} tr[N << 2];
void upd(int p) { tr[p].Min = min(tr[p << 1].Min, tr[p << 1 | 1].Min); }
void build(int p, int l, int r) {
  tr[p].tag = 0;
  if (l == r) {
    tr[p].Min = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  upd(p);
}
void f(int p, int k) {
  tr[p].Min += k;
  tr[p].tag += k;
}
void pushdown(int p, int l, int r) {
  int mid = (l + r) >> 1;
  if (tr[p].tag) {
    f(p << 1, tr[p].tag);
    f(p << 1 | 1, tr[p].tag);
    tr[p].tag = 0;
  }
}
void modify(int p, int l, int r, int nl, int nr, int k) {
  if (l == nl && r == nr) {
    f(p, k);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(p, l, r);
  if (nr <= mid)
    modify(p << 1, l, mid, nl, nr, k);
  else if (nl > mid)
    modify(p << 1 | 1, mid + 1, r, nl, nr, k);
  else
    modify(p << 1, l, mid, nl, mid, k),
        modify(p << 1 | 1, mid + 1, r, mid + 1, nr, k);
  upd(p);
}
int main() {
  ios::sync_with_stdio(0);
  cin >> T;
  while (T--) {
    cin >> n >> m;
    top = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i], st[++top] = a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i], st[++top] = b[i];
    sort(b + 1, b + 1 + m);
    sort(st + 1, st + 1 + top);
    int num = unique(st + 1, st + 1 + top) - st - 1;
    for (int i = 1; i <= num; ++i) M[st[i]] = i;
    for (int i = 1; i <= n; ++i) a[i] = M[a[i]];
    for (int i = 1; i <= m; ++i) b[i] = M[b[i]];
    B.lim = num;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans += B.query(num) - B.query(a[i]);
      B.modify(a[i], 1);
    }
    build(1, 1, n);
    for (int i = 1; i <= n; ++i) head[a[i]].push_back(i);
    int now = 0;
    for (int i = 1; i <= m; ++i) {
      while (now < b[i]) {
        for (int i = 0; i < head[now].size(); ++i)
          modify(1, 1, n, head[now][i], n, -1);
        ++now;
        for (int i = 0; i < head[now].size(); ++i)
          modify(1, 1, n, head[now][i], n, -1);
      }
      int tmp = B.query(b[i] - 1);
      ans += B.query(b[i] - 1);
      int Min = min(tr[1].Min, 0);
      ans += Min;
    }
    cout << ans << endl;
    for (int i = 0; i <= num; ++i) head[i].clear(), B.tr[i] = 0;
  }
  return 0;
}

```