It is the hard version of the problem. The only difference is that in this version 1 ≤ n ≤ 300.

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 (1 ≤ n, 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


7
1 2
1 2
3 2
1 1 2 2 3 3
3 3
3 4 4 1 1 1 1 1 2
2 2
1 1 2 1
4 2
50 50 50 50 3 50 50 50
4 2
6 6 6 6 2 2 9 6
2 9
1 3 3 3 3 3 1 1 3 1 3 1 1 3 3 1 1 3


Output


1
0
4
0
0
0
1

Note

In the first test case, there is a single way to give seats: the first person sits in the first place and the second person — in the second. The total inconvenience is 1.

In the second test case the optimal seating looks like this: 

<image>

In the third test case the optimal seating looks like this: 

<image>

The number in a cell is the person's index that sits on this place.
// Problem: Seating Arrangements (hard version)
// https://codeforces.com/contest/1566/problem/D2
// This submission:
//
// Let there be `rn` rows and `cn` columns of seats in the cinema.
//
// For ease of mapping from seats to row and column indexes, we use 0-based index for seat numbers,
// and row and column indexes. Then, seat index `i` (0-based) is located on row `(i / cn)` and
// column `(i % cn)`.
//
// In the problem definition, the inconvenience _experienced_ by a person `p` is the number of
// people they go through when getting to their seat. This is the number of occupied seats to
// the left of `p`'s seat at the time `p` is seated. Equivalently, we can consider the
// inconvenience _introduced_ by putting `p` in their seat as the number of empty seats to their
// right at the time `p` is seated. For every empty seat to the right, a person will go through
// `p` when getting to their seat in the future.
// Note that the sum of inconvenience experienced (how many people `p` goes through) equals the
// sum of inconvenience introduced (how many people go through `p`). When exploring properties
// of optimal solutions, we may use either one of these definitions, whichever is more convenient
// for the argument.
//
// A `Group` is the set of people with identical sight level `a`.
//
// Lemma 1. The `Group` with minimum sight level and `k[0]` people occupies the first `k[0]` seats.
// Proof of Lemma 1. The `k[0]` people must be seated before the `(rn * cn - k[0])` people from
// other groups (with higher sight level) because of the sight level constraint.
//
// Corollary 2. Lemma 1 places the `k[0]` people in the `Group` with minimum sight level to
// the first `k[0]` seats. If we apply the same argument to the remaining `(rn * cn - k[0])`
// people, then the `k[1]` people in the `Group` with the second smallest sight level (overall)
// must occupy the next `k[1]` seats, or seats `k[0]` to `(k[0] + k[1] - 1)`. Similarly, the `k[2]`
// people with the 3rd smallest sight level (overall) will be seated between `k[0] + k[1]` and
// `(k[0] + k[1] + k[2] - 1)`, inclusive. The case is similar for all `Group`s.
//
// Corollary 2 states that the people from a `Group` must be assigned seats with consecutive
// indexes. Then, the people from a `Group` will:
// (1) Occupy consecutive columns of a row, OR
// (2) Occupy multiple consecutive rows, including the last several columns of the first row
//     (for the `Group`), all columns of the next zero or more rows, and the first several
//     columns of the last row (for the `Group`).
//
// Lemma 3. The people who belong to the same `Group` and seated on the same row should be seated
// from right to left, one seat at a time, in an optimal solution.
// Proof of Lemma 3. Suppose person `p[i]` is seated at `(r, c[i])` when `(r, c[i] + 1)` is an
// empty seat for another person in the same `Group`. Let `p[j]` be the person assigned to
// `(r, c[i] + 1)`. Then, `i < j` because `p[j]`'s seat is empty when `p[i]` is seated (`p[i]` is
// seated first). If we exchange the seat assignments of `p[i]` and `p[j]`, then the sum of
// inconveniences is identical except `p[j]` does not need to go through `p[i]` (after the
// exchange). This results in a better solution. 
//
// Lemma 4. If a `Group` spans multiple rows, we may always fill its first row first in an
// optimal solution.
// Proof of Lemma 4. By Corollary 2 and Lemma 3, the inconvenience experienced by people in the
// `Group` assigned to rows after the first row (of the `Group`) is `0`. Suppose for `i < j`,
// people `p[i]` and `p[j]` belong to the `Group`, `p[i]` is (earlier) seated after the first row
// (with `0` inconvenience experienced) and `p[j]` is (later) seated on the first row (with `x`
// inconvenience experienced). If we exchange the seat assignments of `p[i]` and `p[j]`, `p[i]`
// will experience at most `x` inconvenience because seats occupied to the left of `p[i]` (after
// the exchange) are also occupied for `p[j]` (before the exchange). This is because `p[j]` is
// seated later and occupied seats always remain occupied. `p[j]` experiences `0` inconvenience
// (after the exchange). So, after the exchange we arrive at a solution that is no worse.
//
// Lemma 5. If a `Group` spans multiple rows, we may always fill its last row last in an optimal
// solution.
// Proof of Lemma 5. By Corollary 2 and Lemma 3, the inconvenience introduced by people in the
// `Group` assigned to seats before the last row (of the `Group`) is `0`. Suppose for `i < j`,
// people `p[i]` and `p[j]` belong to the `Group`, `p[i]` is (earlier) seated on the last row
// (with `y` inconvenience introduced) and `p[j]` is (later) seated before the last row (with
// `0` inconvenience introduced). If we exchange seat assignments of `p[i]` and `p[j]`, `p[j]`
// (after the exchange) will introduce at most `y` inconvenience. This is because `p[j]` is seated
// later than `p[i]`, and there will be equal or fewer number of empty seats to the right. This
// is because occupied seats never become empty again. The inconvenience introduced by `p[i]`
// (after the exchange) is `0`. So, after the exchange we arrive at a solution that is no worse.
//
// Putting everything together, by Corollary 2, we order `Group`s by sight level, and then put the
// people of each `Group` with identical sight level in seats with consecutive indexes.
// Within each `Group`:
// If a `Group` occupies only one row, by Lemma 3, we seat them from right to left, one seat at
// a time.
// If a `Group` occupies multiple rows, by Lemmas 4 and 5, we first fill up the first row, then
// we fill up the rows in between first and last (both exclusive), and we fill up the last row
// last. We follow Lemma 3 to fill up each row from right to left, one seat at a time.
// So, the exact seat of every person is determined.

import java.util.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;

public class SeatingArrangements {

  private static class Group {
    // The sight level of people in this `Group`.
    private int a;

    // The seat indexes people in this `Group` should be seated at, inclusive.
    private int low, high;
    
    // The first and last row(s) that people in this `Group` occupy. Note that by Corollary 2,
    // rows in between first and last (both exclusive) are fully filled by people from this
    // `Group`.
    private int firstRow, lastRow;

    // The number of empty seats remaining for the `Group` on the first and last rows, and overall.
    private int firstRowEmptySeats, lastRowEmptySeats, emptySeats;
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int testCasesCount = in.nextInt();
    for (int testCase = 1; testCase <= testCasesCount; ++testCase) {
      int rn = in.nextInt();
      int cn = in.nextInt();

      // The sight level of people entering the cinema, in the order they are seated.
      int[] a = new int[rn * cn];

      // Mapping from sight level to the number of people with that sight level.
      TreeMap<Integer, Integer> aToCount = new TreeMap<>();

      for (int i = 0; i < a.length; ++i) {
        a[i] = in.nextInt();

        if (aToCount.containsKey(a[i])) {
          aToCount.put(a[i], aToCount.get(a[i]) + 1);
        } else {
          aToCount.put(a[i], 1);
        }
      }

      // Mapping from the sight level of a person to the `Group` they belong to.
      Map<Integer, Group> groups = new HashMap<>();

      int low = 0;
      for (Map.Entry<Integer, Integer> aAndCount : aToCount.entrySet()) {
        Group group = new Group();
        group.a = aAndCount.getKey();
        group.emptySeats = aAndCount.getValue();

        group.low = low;
        group.high = low + aAndCount.getValue() - 1;
        group.firstRow = (group.low / cn);
        group.lastRow = (group.high / cn);

        if (group.firstRow < group.lastRow) {
          group.firstRowEmptySeats = (cn - 1) - (group.low % cn) + 1;
          group.lastRowEmptySeats = (group.high % cn) + 1;
        } else {
          group.firstRowEmptySeats = group.lastRowEmptySeats = group.emptySeats;
        }

        groups.put(group.a, group);
        low = group.high + 1;
      }

      // The cell `empty[r][c]` indicates if the seat at `(r, c)` is still empty.
      boolean[][] empty = new boolean[rn][cn];
      for (int r = 0; r < rn; ++r) {
        Arrays.fill(empty[r], true);
      }

      int result = 0;
      for (int i = 0; i < a.length; ++i) {
        Group group = groups.get(a[i]);

        if (group.firstRow == group.lastRow) {
          // Put the person at the last spot of the only row (Lemma 3).
          int c = getLastEmpty(empty[group.firstRow], group.high % cn);
          empty[group.firstRow][c] = false;
          result += getInconvenienceIntroduced(empty[group.firstRow], group.high % cn + 1);

          group.firstRowEmptySeats--;
          group.lastRowEmptySeats--;
        } else {
          if (group.firstRowEmptySeats > 0) {
            // Put people on the first row first (Lemma 4).
            int c = getLastEmpty(empty[group.firstRow], cn - 1);
            empty[group.firstRow][c] = false;
            group.firstRowEmptySeats--;
          } else if (group.emptySeats > group.lastRowEmptySeats) {
            // Put the person in the rows in between. These rows are fully filled up by people from
            // the same `Group` (Corollary 2), from right to left, one seat at a time (Lemma 3).
            // So, they never experience any inconvenience. We don't need to keep track of
            // `empty` state for these rows.
          } else {
            // Put people on the last row last (Lemma 5).
            int c = getLastEmpty(empty[group.lastRow], group.high % cn);
            empty[group.lastRow][c] = false;
            result += getInconvenienceIntroduced(empty[group.lastRow], group.high % cn + 1);
            group.lastRowEmptySeats--;
          }
        }
        group.emptySeats--;
      }

      System.out.println(result);
    }

    in.close();
  }

  private static int getLastEmpty(boolean[] empty, int c) {
    while (c >= 0) {
      if (empty[c]) {
        return c;
      }
      --c;
    }

    return c;
  }

  private static int getInconvenienceIntroduced(boolean[] empty, int c) {
    int count = 0;
    while (c < empty.length) {
      if (empty[c]) {
        ++count;
      }
      ++c;
    }
    return count;
  }
}