It is the easy version of the problem. The only difference is that in this version n = 1.

In the cinema seats can be represented as the table with n rows and m columns. The rows are numbered with integers from 1 to n. The seats in each row are numbered with consecutive integers from left to right: in the k-th row from m (k - 1) + 1 to m k for all rows 1 ≤ k ≤ n.

1| 2| ⋅⋅⋅| m - 1| m  
---|---|---|---|---  
m + 1| m + 2| ⋅⋅⋅| 2 m - 1| 2 m  
2m + 1| 2m + 2| ⋅⋅⋅| 3 m - 1| 3 m  
\vdots| \vdots| \ddots| \vdots| \vdots  
m (n - 1) + 1| m (n - 1) + 2| ⋅⋅⋅| n m - 1| n m  
The table with seats indices

There are nm people who want to go to the cinema to watch a new film. They are numbered with integers from 1 to nm. You should give exactly one seat to each person.

It is known, that in this cinema as lower seat index you have as better you can see everything happening on the screen. i-th person has the level of sight a_i. Let's define s_i as the seat index, that will be given to i-th person. You want to give better places for people with lower sight levels, so for any two people i, j such that a_i < a_j it should be satisfied that s_i < s_j.

After you will give seats to all people they will start coming to their seats. In the order from 1 to nm, each person will enter the hall and sit in their seat. To get to their place, the person will go to their seat's row and start moving from the first seat in this row to theirs from left to right. While moving some places will be free, some will be occupied with people already seated. The inconvenience of the person is equal to the number of occupied seats he or she will go through.

Let's consider an example: m = 5, the person has the seat 4 in the first row, the seats 1, 3, 5 in the first row are already occupied, the seats 2 and 4 are free. The inconvenience of this person will be 2, because he will go through occupied seats 1 and 3.

Find the minimal total inconvenience (the sum of inconveniences of all people), that is possible to have by giving places for all people (all conditions should be satisfied).

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers n and m (n = 1, 1 ≤ m ≤ 300) — the number of rows and places in each row respectively.

The second line of each test case contains n ⋅ m integers a_1, a_2, …, a_{n ⋅ m} (1 ≤ a_i ≤ 10^9), where a_i is the sight level of i-th person.

It's guaranteed that the sum of n ⋅ m over all test cases does not exceed 10^5.

Output

For each test case print a single integer — the minimal total inconvenience that can be achieved.

Example

Input


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


Output


3
6
0
1

Note

In the first test case, there is a single way to arrange people, because all sight levels are distinct. The first person will sit on the first seat, the second person will sit on the second place, the third person will sit on the third place. So inconvenience of the first person will be 0, inconvenience of the second person will be 1 and inconvenience of the third person will be 2. The total inconvenience is 0 + 1 + 2 = 3.

In the second test case, people should sit as follows: s_1 = 2, s_2 = 1, s_3 = 5, s_4 = 4, s_5 = 3. The total inconvenience will be 6.
import java.io.*;
import java.util.*;

public class Solution {
    static FastScanner fs;
    static PrintWriter pw;
    public static void main(String[] args) {
        fs = new FastScanner();
        pw = new PrintWriter(System.out);
        precomp();
        int t = fs.nextInt();
        while (t-- > 0)
            solve();
        pw.close();
    }
    public static void precomp() {

    }
    public static void solve() {
        int n = fs.nextInt();
        int m = fs.nextInt();
        int[] a = new int[n*m];
        for (int i=0; i<n*m; i++)
            a[i] = fs.nextInt();
        int[] b = a.clone();
        Arrays.sort(a);
        int[][] arr = new int[n][m];
        for (int i=0; i<n; i++) for (int j=0; j<m; j++) arr[i][j] = a[m*i+j];
        boolean[][] done = new boolean[n][m];
        SegmentTree[] segtrees = new SegmentTree[n];
        int[] temp = new int[m];
        for (int i=0; i<n; i++)
            segtrees[i] = new SegmentTree(temp);
        int ans = 0;
        out: for (int itb=0; itb<n*m; itb++) {
            int find = b[itb];
            int lo = 0, hi = n*m-1;
            for (--lo; lo < hi; ) {
                int mid = lo+(hi-lo+1)/2;
                if (a[mid]<=find) lo = mid;
                else hi = mid-1;
            }
            int up = lo/m;
            lo = 0;
            hi = n*m-1;
            for (hi ++; lo < hi; ) {
                int mid = lo+(hi-lo)/2;
                if (a[mid]>=find) hi = mid;
                else lo = mid+1;
            }
            int down = lo/m;
            for (int i=down; i<=up; i++) {
                for (int j=m-1; j>=0; j--) {
                    if (!done[i][j] && arr[i][j]==b[itb]) {
                        done[i][j] = true;
                        ans += segtrees[i].rsq(0, j);
                        segtrees[i].update(j, j, 1);
                        continue out;
                    }
                }
            }
        }
        pw.println(ans);
    }
    static class pair {
        long lo, hi;
        pair (long x, long y) {lo=x; hi=y;}
    }
    static long pow(long b, long exp, long mod) {
        long ret = 1;
        while (exp > 0) {
            if ((exp & 1) > 0)
                ret = (ret * b) % mod;
            b = (b * b) % mod;
            exp >>= 1;
        }
        return ret;
    }
    //    static int k;
//    static int par(int curr) {
//        return (1<<k)-1-(((1<<k)-1-curr)/2);
//    }
//    static int left(int curr) {
//        return (1<<k)-1-(2*((1<<k)-1-curr)+1);
//    }
//    static int right(int curr) {
//        return (1<<k)-1-(2*((1<<k)-1-curr));
//    }
    static int gcd(int a, int b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }

    static void ruffleSort(int[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n), temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }

    static final Random random = new Random();

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static int[] reverse(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = a[n - 1 - i];
        return res;
    }
    static class Node {
        int sum;
        int min;
        //Here We store the value that will be propagated lazily
        Integer pendingVal = null;
        int from;
        int to;

        int size() {
            return to - from + 1;
        }

    }
    static class SegmentTree {

        private Node[] heap;
        private int[] array;
        private int size;

        /**
         * Time-Complexity:  O(n*log(n))
         *
         * @param array the Initialization array
         */
        public SegmentTree(int[] array) {
            this.array = Arrays.copyOf(array, array.length);
            //The max size of this array is about 2 * 2 ^ log2(n) + 1
            size = (int) (2 * Math.pow(2.0, Math.floor((Math.log((double) array.length) / Math.log(2.0)) + 1)));
            heap = new Node[size];
            build(1, 0, array.length);
        }


        public int size() {
            return array.length;
        }

        //Initialize the Nodes of the Segment tree
        private void build(int v, int from, int size) {
            heap[v] = new Node();
            heap[v].from = from;
            heap[v].to = from + size - 1;

            if (size == 1) {
                heap[v].sum = array[from];
                heap[v].min = array[from];
            } else {
                //Build childs
                build(2 * v, from, size / 2);
                build(2 * v + 1, from + size / 2, size - size / 2);

                heap[v].sum = heap[2 * v].sum + heap[2 * v + 1].sum;
                //min = min of the children
                heap[v].min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
            }
        }

        /**
         * Range Sum Query
         *
         * Time-Complexity: O(log(n))
         *
         * @param  from from index
         * @param  to to index
         * @return sum
         */
        public int rsq(int from, int to) {
            return rsq(1, from, to);
        }

        private int rsq(int v, int from, int to) {
            Node n = heap[v];

            //If you did a range update that contained this node, you can infer the Sum without going down the tree
            if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
                return (to - from + 1) * n.pendingVal;
            }

            if (contains(from, to, n.from, n.to)) {
                return heap[v].sum;
            }

            if (intersects(from, to, n.from, n.to)) {
                propagate(v);
                int leftSum = rsq(2 * v, from, to);
                int rightSum = rsq(2 * v + 1, from, to);

                return leftSum + rightSum;
            }

            return 0;
        }

        /**
         * Range Min Query
         *
         * Time-Complexity: O(log(n))
         *
         * @param  from from index
         * @param  to to index
         * @return min
         */
        public int rMinQ(int from, int to) {
            return rMinQ(1, from, to);
        }

        private int rMinQ(int v, int from, int to) {
            Node n = heap[v];


            //If you did a range update that contained this node, you can infer the Min value without going down the tree
            if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
                return n.pendingVal;
            }

            if (contains(from, to, n.from, n.to)) {
                return heap[v].min;
            }

            if (intersects(from, to, n.from, n.to)) {
                propagate(v);
                int leftMin = rMinQ(2 * v, from, to);
                int rightMin = rMinQ(2 * v + 1, from, to);

                return Math.min(leftMin, rightMin);
            }

            return Integer.MAX_VALUE;
        }


        /**
         * Range Update Operation.
         * With this operation you can update either one position or a range of positions with a given number.
         * The update operations will update the less it can to update the whole range (Lazy Propagation).
         * The values will be propagated lazily from top to bottom of the segment tree.
         * This behavior is really useful for updates on portions of the array
         * <p>
         * Time-Complexity: O(log(n))
         *
         * @param from  from index
         * @param to    to index
         * @param value value
         */
        public void update(int from, int to, int value) {
            update(1, from, to, value);
        }

        private void update(int v, int from, int to, int value) {

            //The Node of the heap tree represents a range of the array with bounds: [n.from, n.to]
            Node n = heap[v];

            /**
             * If the updating-range contains the portion of the current Node  We lazily update it.
             * This means We do NOT update each position of the vector, but update only some temporal
             * values into the Node; such values into the Node will be propagated down to its children only when they need to.
             */
            if (contains(from, to, n.from, n.to)) {
                change(n, value);
            }

            if (n.size() == 1) return;

            if (intersects(from, to, n.from, n.to)) {
                /**
                 * Before keeping going down to the tree We need to propagate the
                 * the values that have been temporally/lazily saved into this Node to its children
                 * So that when We visit them the values  are properly updated
                 */
                propagate(v);

                update(2 * v, from, to, value);
                update(2 * v + 1, from, to, value);

                n.sum = heap[2 * v].sum + heap[2 * v + 1].sum;
                n.min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
            }
        }

        //Propagate temporal values to children
        private void propagate(int v) {
            Node n = heap[v];

            if (n.pendingVal != null) {
                change(heap[2 * v], n.pendingVal);
                change(heap[2 * v + 1], n.pendingVal);
                n.pendingVal = null; //unset the pending propagation value
            }
        }

        //Save the temporal values that will be propagated lazily
        private void change(Node n, int value) {
            n.pendingVal = value;
            n.sum = n.size() * value;
            n.min = value;
            array[n.from] = value;

        }

        //Test if the range1 contains range2
        private boolean contains(int from1, int to1, int from2, int to2) {
            return from2 >= from1 && to2 <= to1;
        }
        //check inclusive intersection, test if range1[from1, to1] intersects range2[from2, to2]
        private boolean intersects(int from1, int to1, int from2, int to2) {
            return from1 <= from2 && to1 >= from2   //  (.[..)..] or (.[...]..)
                    || from1 >= from2 && from1 <= to2; // [.(..]..) or [..(..)..
        }
    }
}