#include <bits/stdc++.h>
using namespace std;
namespace Input {
inline char Sc() {
  static const int LEN = 100000;
  static char Buf[LEN], *OP = Buf, *ED = Buf;
  if (OP == ED) {
    ED = (OP = Buf) + fread(Buf, 1, LEN, stdin);
    if (OP == ED) return -1;
  }
  return *OP++;
}
template <class T>
inline bool rd(T &x) {
  static char c, f;
  f = 1;
  for (x = 0, c = Sc(); c < 48; c = Sc()) {
    if (!~c) return 0;
    if (!(c ^ '-')) f = -1;
  }
  for (; c > 47; c = Sc()) x = (x << 1) + (x << 3) + (c ^ 48);
  x *= f;
  return 1;
}
}  // namespace Input
int A[1000010], B[1000010], C[1000010 << 1], E[1000010 << 1];
int n, m, h;
struct edge {
  int nxt, t;
} e[1000010 << 1];
int head[1000010 << 1], edge_cnt;
void add_edge(int x, int y) {
  e[edge_cnt] = (edge){head[x], y};
  head[x] = edge_cnt++;
}
struct Segment_Tree {
  int Mn[1000010 << 2], Upd[1000010 << 2];
  void build(int l, int r, int p) {
    Upd[p] = 0;
    Mn[p] = l - 1;
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, (p << 1));
    build(mid + 1, r, (p << 1 | 1));
  }
  void Update(int l, int r, int p, int pl, int pr, int x) {
    if (pl > pr) {
      return;
    }
    if (l == pl && r == pr) {
      Upd[p] += x;
      Mn[p] += x;
      return;
    }
    int mid = (l + r) >> 1;
    if (Upd[p]) {
      Upd[(p << 1)] += Upd[p];
      Upd[(p << 1 | 1)] += Upd[p];
      Mn[(p << 1)] += Upd[p];
      Mn[(p << 1 | 1)] += Upd[p];
      Upd[p] = 0;
    }
    if (pr <= mid) {
      Update(l, mid, (p << 1), pl, pr, x);
    } else if (pl > mid) {
      Update(mid + 1, r, (p << 1 | 1), pl, pr, x);
    } else {
      Update(l, mid, (p << 1), pl, mid, x);
      Update(mid + 1, r, (p << 1 | 1), mid + 1, pr, x);
    }
    Mn[p] = min(Mn[(p << 1)], Mn[(p << 1 | 1)]);
  }
} T;
struct Binary_Indexed_Tree {
  int bit[1000010 << 1];
  void Add(int i) {
    while (i > 0) {
      bit[i]++;
      i -= i & -i;
    }
  }
  int Query(int i) {
    int res = 0;
    while (i <= h) {
      res += bit[i];
      i += i & -i;
    }
    return res;
  }
} BIT;
int main() {
  int Case;
  Input::rd(Case);
  while (Case--) {
    Input::rd(n);
    Input::rd(m);
    int i, j;
    for (i = 1; i <= n; i++) {
      Input::rd(A[i]);
      C[i] = A[i];
    }
    for (i = 1; i <= m; i++) {
      Input::rd(B[i]);
      C[i + n] = B[i];
    }
    sort(C + 1, C + 1 + n + m);
    h = unique(C + 1, C + 1 + n + m) - C - 1;
    for (i = 1; i <= h; i++) {
      E[i] = 0;
    }
    memset(head + 1, -1, sizeof(int) * h);
    edge_cnt = 0;
    for (i = 1; i <= n; i++) {
      A[i] = lower_bound(C + 1, C + 1 + h, A[i]) - C;
      add_edge(A[i], i);
    }
    for (i = 1; i <= m; i++) {
      B[i] = lower_bound(C + 1, C + 1 + h, B[i]) - C;
      E[B[i]]++;
    }
    long long Ans = 0;
    memset(BIT.bit + 1, 0, sizeof(int) * h);
    for (i = 1; i <= n; i++) {
      Ans += BIT.Query(A[i]);
      BIT.Add(A[i] - 1);
    }
    T.build(1, n, 1);
    for (i = 1; i <= h; i++) {
      for (j = head[i]; ~j; j = e[j].nxt) {
        int x = e[j].t;
        T.Update(1, n, 1, x + 1, n, -1);
      }
      Ans += 1LL * E[i] * T.Mn[1];
      for (j = head[i]; ~j; j = e[j].nxt) {
        int x = e[j].t;
        T.Update(1, n, 1, 1, x - 1, 1);
      }
    }
    printf("%lld\n", Ans);
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
namespace Input {
inline char Sc() {
  static const int LEN = 100000;
  static char Buf[LEN], *OP = Buf, *ED = Buf;
  if (OP == ED) {
    ED = (OP = Buf) + fread(Buf, 1, LEN, stdin);
    if (OP == ED) return -1;
  }
  return *OP++;
}
template <class T>
inline bool rd(T &x) {
  static char c, f;
  f = 1;
  for (x = 0, c = Sc(); c < 48; c = Sc()) {
    if (!~c) return 0;
    if (!(c ^ '-')) f = -1;
  }
  for (; c > 47; c = Sc()) x = (x << 1) + (x << 3) + (c ^ 48);
  x *= f;
  return 1;
}
}  // namespace Input
int A[1000010], B[1000010], C[1000010 << 1], E[1000010 << 1];
int n, m, h;
struct edge {
  int nxt, t;
} e[1000010 << 1];
int head[1000010 << 1], edge_cnt;
void add_edge(int x, int y) {
  e[edge_cnt] = (edge){head[x], y};
  head[x] = edge_cnt++;
}
struct Segment_Tree {
  int Mn[1000010 << 2], Upd[1000010 << 2];
  void build(int l, int r, int p) {
    Upd[p] = 0;
    Mn[p] = l - 1;
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, (p << 1));
    build(mid + 1, r, (p << 1 | 1));
  }
  void Update(int l, int r, int p, int pl, int pr, int x) {
    if (pl > pr) {
      return;
    }
    if (l == pl && r == pr) {
      Upd[p] += x;
      Mn[p] += x;
      return;
    }
    int mid = (l + r) >> 1;
    if (Upd[p]) {
      Upd[(p << 1)] += Upd[p];
      Upd[(p << 1 | 1)] += Upd[p];
      Mn[(p << 1)] += Upd[p];
      Mn[(p << 1 | 1)] += Upd[p];
      Upd[p] = 0;
    }
    if (pr <= mid) {
      Update(l, mid, (p << 1), pl, pr, x);
    } else if (pl > mid) {
      Update(mid + 1, r, (p << 1 | 1), pl, pr, x);
    } else {
      Update(l, mid, (p << 1), pl, mid, x);
      Update(mid + 1, r, (p << 1 | 1), mid + 1, pr, x);
    }
    Mn[p] = min(Mn[(p << 1)], Mn[(p << 1 | 1)]);
  }
} T;
struct Binary_Indexed_Tree {
  int bit[1000010 << 1];
  void Add(int i) {
    while (i > 0) {
      bit[i]++;
      i -= i & -i;
    }
  }
  int Query(int i) {
    int res = 0;
    while (i <= h) {
      res += bit[i];
      i += i & -i;
    }
    return res;
  }
} BIT;
int main() {
  int Case;
  Input::rd(Case);
  while (Case--) {
    Input::rd(n);
    Input::rd(m);
    int i, j;
    for (i = 1; i <= n; i++) {
      Input::rd(A[i]);
      C[i] = A[i];
    }
    for (i = 1; i <= m; i++) {
      Input::rd(B[i]);
      C[i + n] = B[i];
    }
    sort(C + 1, C + 1 + n + m);
    h = unique(C + 1, C + 1 + n + m) - C - 1;
    for (i = 1; i <= h; i++) {
      E[i] = 0;
    }
    memset(head + 1, -1, sizeof(int) * h);
    edge_cnt = 0;
    for (i = 1; i <= n; i++) {
      A[i] = lower_bound(C + 1, C + 1 + h, A[i]) - C;
      add_edge(A[i], i);
    }
    for (i = 1; i <= m; i++) {
      B[i] = lower_bound(C + 1, C + 1 + h, B[i]) - C;
      E[B[i]]++;
    }
    long long Ans = 0;
    memset(BIT.bit + 1, 0, sizeof(int) * h);
    for (i = 1; i <= n; i++) {
      Ans += BIT.Query(A[i]);
      BIT.Add(A[i] - 1);
    }
    T.build(1, n, 1);
    for (i = 1; i <= h; i++) {
      for (j = head[i]; ~j; j = e[j].nxt) {
        int x = e[j].t;
        T.Update(1, n, 1, x + 1, n, -1);
      }
      Ans += 1LL * E[i] * T.Mn[1];
      for (j = head[i]; ~j; j = e[j].nxt) {
        int x = e[j].t;
        T.Update(1, n, 1, 1, x - 1, 1);
      }
    }
    printf("%lld\n", Ans);
  }
  return 0;
}

```