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>
using namespace std;
using ll = long long;
using Vi = vector<int>;
using Pii = pair<int, int>;
int uplg(int n) { return 32 - __builtin_clz(n); }
int uplg(ll n) { return 64 - __builtin_clzll(n); }
Vi compressVec(vector<int*>& vec) {
  sort((vec).begin(), (vec).end(), [](int* l, int* r) { return *l < *r; });
  Vi old;
  for (auto& e : (vec)) {
    if (old.empty() || old.back() != *e) old.push_back(*e);
    *e = int((old).size()) - 1;
  }
  return old;
}
ll countInversions(Vi perm) {
  ll ret = 0, cont = 1;
  Vi odd;
  while (cont) {
    odd.assign(int((perm).size()) + 1, 0);
    cont = 0;
    for (int i = (0); i < (int((perm).size())); i++) {
      if (perm[i] % 2)
        odd[perm[i]]++;
      else
        ret += odd[perm[i] + 1];
      cont += perm[i] /= 2;
    }
  }
  return ret;
}
ll cntInvA(vector<int> A) {
  vector<int*> aRef(int((A).size()));
  for (int i = 0; i < int((A).size()); i++) {
    aRef[i] = &A[i];
  }
  compressVec(aRef);
  return countInversions(A);
}
const int inf = 1e9;
struct Tree {
  int base = 1;
  vector<int> lazy, mini;
  int len = 0;
  Tree(int n) {
    while (base < n + 3) base *= 2;
    mini.resize(2 * base);
    lazy.resize(2 * base);
  }
  void apply(int a, int c) {
    mini[a] += c;
    lazy[a] += c;
  }
  void update(int a) { mini[a] = min(mini[2 * a], mini[2 * a + 1]); }
  void push(int a) {
    apply(2 * a, lazy[a]);
    apply(2 * a + 1, lazy[a]);
    lazy[a] = 0;
  }
  void modify(int a, int nl, int nr, int ql, int qr, int c) {
    if (nr < ql || qr < nl) return;
    if (ql <= nl && nr <= qr) {
      apply(a, c);
      return;
    }
    push(a);
    int mid = (nl + nr) / 2;
    modify(2 * a, nl, mid, ql, qr, c);
    modify(2 * a + 1, mid + 1, nr, ql, qr, c);
    update(a);
  }
  void plusSeg(int ql, int qr, int c) { modify(1, 0, base - 1, ql, qr, c); }
  int queryMin(int a, int nl, int nr, int ql, int qr) {
    if (nr < ql || qr < nl) return inf;
    if (ql <= nl && nr <= qr) {
      return mini[a];
    }
    push(a);
    int mid = (nl + nr) / 2;
    return min(queryMin(2 * a, nl, mid, ql, qr),
               queryMin(2 * a + 1, mid + 1, nr, ql, qr));
  }
  int query(int ql, int qr) { return queryMin(1, 0, base - 1, ql, qr); }
};
struct Event {
  int val, type, pos;
  bool operator<(const Event& e) const {
    return Pii(val, type) < Pii(e.val, e.type);
  }
};
void run() {
  int n, m;
  cin >> n >> m;
  vector<int> A(n), B(m);
  for (auto& first : (A)) cin >> first;
  for (auto& first : (B)) cin >> first;
  sort((B).begin(), (B).end());
  ll resA = cntInvA(A);
  Tree tree(n + 1);
  for (int i = 0; i < n; i++) {
    tree.plusSeg(i + 1, n, 1);
  }
  vector<Event> events;
  for (int i = 0; i < n; i++) {
    events.push_back({A[i], -1, i + 1});
    events.push_back({A[i], 1, i + 1});
  }
  for (int i = 0; i < m; i++) {
    events.push_back({B[i], 0, -1});
  }
  sort((events).begin(), (events).end());
  ll resB = 0;
  for (Event e : events) {
    if (e.type == -1) {
      tree.plusSeg(e.pos, n, -1);
    } else if (e.type == 0) {
      resB += tree.query(0, n);
    } else if (e.type == 1) {
      tree.plusSeg(0, e.pos - 1, 1);
    }
  }
  cout << resA + resB << "\n";
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(18);
  int t = 1;
  cin >> t;
  for (int i = (0); i < (t); i++) {
    run();
  }
  return 0;
}
