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]. 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author afhi
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        COptimalInsertion solver = new COptimalInsertion();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class COptimalInsertion {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int m = in.readInt();
            int[] b = new int[m + 2];
            COptimalInsertion.Pair[] ps = new COptimalInsertion.Pair[n];
            for (int i = 0; i < n; i++) {
                ps[i] = new COptimalInsertion.Pair(in.readInt(), i);
            }

            for (int i = 1; i <= m; i++) {
                b[i] = in.readInt();
            }

            b[0] = Integer.MIN_VALUE;
            b[m + 1] = Integer.MAX_VALUE;
            Arrays.sort(b);
            Arrays.sort(ps);

            COptimalInsertion.SegTree tree = new COptimalInsertion.SegTree(n);
            for (int i = 0; i < n; i++) {
                tree.update(i, -1, 0);
            }
            long ans = 0;
            int cnt1 = 0; // the number of 1s
            for (int i = 1; i <= m; i++) {
                if (b[i - 1] != b[i]) {
                    while (cnt1 < n && ps[cnt1].p1 < b[i]) {
                        tree.update(ps[cnt1].p2, 1, 1);
                        cnt1++;
                    }
                    int k = cnt1;
                    while (k < n && ps[k].p1 == b[i]) {
                        tree.update(ps[k].p2, 0, 0);
                        k++;
                    }
                }
                ans += cnt1 - tree.query();
            }

            int idx = 0;
            int cur = 0;
            int[] pos = new int[n];
            while (cur < n) {
                int x = ps[cur].p1;
                while (cur < n && ps[cur].p1 == x) {
                    pos[ps[cur++].p2] = idx;
                }
                idx++;
            }
            COptimalInsertion.FT fenwickTree = new COptimalInsertion.FT(idx);
            for (int i = 0; i < n; i++) {
                int j = pos[i];
                ans += fenwickTree.query(idx) - fenwickTree.query(j + 1);
                fenwickTree.update(j, 1);
            }
            out.printLine(ans);
        }

        static class SegTree {
            int n;
            int[] s1;
            int[] s2;

            public SegTree(int n_) {
                int x = 1;
                while (x < n_) x *= 2;
                this.n = x;
                s1 = new int[2 * n];
                s2 = new int[2 * n];
                for (int i = 0; i < 2 * n; i++) {
                    s1[i] = 0;
                    s2[i] = 0;
                }
            }

            void combine(int pos, int l, int r) {
                s1[pos] = s1[l] + s1[r];
                s2[pos] = Math.max(s1[l] + s2[r], s2[l]);
            }

            void update(int pos, int val1, int val2) {
                s1[pos + n] = val1;
                s2[pos + n] = val2;
                pos = (pos + n) / 2;
                for (; pos != 0; pos /= 2) {
                    combine(pos, pos << 1, pos << 1 | 1);
                }
            }

            int query() {
                return s2[1];
            }

        }

        static class FT {
            int[] s;

            public FT(int n) {
                s = new int[n];
            }

            void update(int pos, int dif) {
                for (; pos < s.length; pos |= pos + 1) s[pos] += dif;
            }

            int query(int pos) {
                int res = 0;
                for (; pos > 0; pos &= pos - 1) res += s[pos - 1];
                return res;
            }

        }

        static class Pair implements Comparable<COptimalInsertion.Pair> {
            int p1;
            int p2;

            public Pair(int x, int y) {
                p1 = x;
                p2 = y;
            }

            public int compareTo(COptimalInsertion.Pair pair) {
                return Integer.compare(this.p1, pair.p1);
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            boolean isSpaceChar(int ch);

        }

    }
}

