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.
import java.util.*;
import java.io.*;

public class codeforces {
	static long[]fac=new long[200100];
	static long[] two= new long[200100] ;
	static long mod=((int)1e9)+7;
	static String[]pow=new String[63];
	static int[][]perm;
	static int[]pe,aa;
	static int x=0;
	static int n,r,m,w,s,h,k;
	static long[][][]memo;
	static int[]val,b,c,time;
	static String t;
	static long[][]bonus;
	static ArrayList<Pair>nuts;
	static Pair[]a;
	static HashMap<String, sv>[]hm;
	public static void main(String[] args) throws IOException{
		int t=sc.nextInt();
		while(t-->0) {
			int n=sc.nextInt();
			int m=sc.nextInt();
			long[]a=new long[m*n];
			long[]idx=new long[m*n];
			for (int i = 0; i < a.length; i++) {
				a[i]=sc.nextLong();
				idx[i]=i;
			}
			sortIdx(a, idx);
			int r=0;
			for (int i = 0; i < idx.length; i++) {
				for (int j = i+1; j < (i/m+1)*m; j++) {
					if(a[j]>a[i]&&idx[j]>idx[i])r++;
				}
			}
			pw.println(r);
		}	
		pw.close();
	}
	
	
	public static long dp(int i,int j,int k) {
		if(i==j&&j==k&&j==n)return 1;
		else if(i+j+k==3*n-1)return 0;
		if(memo[i][j][k]!=-1)return memo[i][j][k];
		long t1=0,t2=0,t3=0,t4=0,t5=0;
		if(i==j&&i<n)t1=dp(i+1,j+1,k);
		if(j==k&&j<n)t2=dp(i,j+1,k+1);
		if(i<n-1)t3=dp(i+2,j,k);
		if(j<n-1)t4=dp(i,j+2,k);
		if(k<n-1)t5=dp(i,j,k+2);
		pw.println(i+" "+" "+j+" "+k+" "+(t1+t2+t3+t4+t5));
		return memo[i][j][k]=t1+t2+t3+t4+t5;
	}
	
//	static Stack<StringBuilder>res=new Stack<StringBuilder>();
//	public static void trace(int idx,int msk) {
//		if(idx==n) {
//			while(res.size()>1) {
//				StringBuilder b=res.pop();
//				StringBuilder a=res.pop();
//				StringBuilder c=new StringBuilder("(");
//				c.append(a);
//				c.append(" x ");
//				c.append(b);
//				c.append(")");
//				res.push(c);
//			}
//			return;
//		}
//		long take=Long.MAX_VALUE;
//		long delay=Long.MAX_VALUE;
//		long prev=Long.MAX_VALUE;
//		long d=a[idx].x;
//		int i= 2*idx-2;
//		for (  ; i >= 0; i--) {
//			if((msk&1<<i)==0) {
////				prev=d*a[i/2].x*a[i/2].y+sol(idx,msk|1<<i);
//				break;
//			}
//		}
//		int x=msk;
//		take=a[(i+1)/2].x*a[idx].x*a[idx].y+sol(idx+1,(x|1<<(2*idx-1))|1<<(2*idx));
//		delay=sol(idx+1,msk|1<<(2*idx));
//		if(memo[idx][msk]==delay) {
//			StringBuilder c=new StringBuilder("A");
//			c.append(""+(idx+1));
//			res.push(c);
//			trace(idx+1,msk|1<<(2*idx));
//		}else if(memo[idx][msk]==take) {
//			StringBuilder a=res.pop();
//			StringBuilder c=new StringBuilder("(");
//			c.append(a);
//			c.append(" x ");
//			c.append("A");
//			c.append(""+(idx+1));
//			c.append(")");
//			res.push(c);
//			trace(idx+1,(x|1<<(2*idx-1))|1<<(2*idx));
//		}else {
//			StringBuilder b=res.pop();
//			StringBuilder a=res.pop();
//			StringBuilder c=new StringBuilder("(");
//			c.append(a);
//			c.append(" x ");
//			c.append(b);
//			c.append(")");
//			res.push(c);
//			trace(idx,msk|1<<i);
//		}
//	}
//	
//	public static long sol(int idx,int msk) {
//		if(memo[idx][msk]!=-1)return memo[idx][msk];
//
//		if(idx==n) {
//			long d=a[n-1].y;
//			long r=0;
//			for (int i = 2*idx-2; i >= 0; i--) {
//				if((msk&1<<i)==0) {
//					int j;
//					for (j = i-1; j >=0; j--) {
//						if((msk&1<<j)==0)break;
//					}
//					r+=a[(j+1)/2].x*a[i/2].y*d;
//					msk=msk|1<<i;
//				}
//			}
//			return memo[idx][msk]=r;
//		}
//		long take=Long.MAX_VALUE;
//		long delay=Long.MAX_VALUE;
//		long prev=Long.MAX_VALUE;
//		long d=a[idx].x;
//		int i= 2*idx-2;
//		for (  ; i >= 0; i--) {
//			if((msk&1<<i)==0) {
//				prev=d*a[i/2].x*a[i/2].y+sol(idx,msk|1<<i);
//				break;
//			}
//		}
//		int x=msk;
//		take=a[(i+1)/2].x*a[idx].x*a[idx].y+sol(idx+1,(x|1<<(2*idx-1))|1<<(2*idx));
//		delay=sol(idx+1,msk|1<<(2*idx));
//		return memo[idx][msk]=Math.min(prev, Math.min(delay, take));
//	}
	
	
	public static int LIS(int[] a) {

		int n = a.length;
		int[] ser = new int[n];
		int[]ser1=new int[n];
		Arrays.fill(ser1, Integer.MAX_VALUE);
		Arrays.fill(ser, Integer.MAX_VALUE);
		int cur = -1;
		int[]inc=new int[n];
		int[]dec=new int[n];
		for (int i = 0; i < n; i++) {
			int low = 0;
			int high = n - 1;
			int mid = (low + high) / 2;
			while (low <= high) {
				if (ser[mid] < a[i]) {
					low = mid + 1;
				} else {
					high = mid - 1;
				}
				mid = (low + high) / 2;
			}
			inc[i]=high+2;
			cur = Math.max(cur, high + 1);
			ser[high + 1] = Math.min(ser[high + 1], a[i]);
		}
		for (int i = n-1; i >= 0; i--) {
			int low = 0;
			int high = n - 1;
			int mid = (low + high) / 2;
			while (low <= high) {
				if (ser1[mid] < a[i]) {
					low = mid + 1;
				} else {
					high = mid - 1;
				}
				mid = (low + high) / 2;
			}
			dec[i]=high+2;
			cur = Math.max(cur, high + 1);
			ser1[high + 1] = Math.min(ser1[high + 1], a[i]);
		}
		int ans=1;
		for (int i = 0; i < dec.length; i++) {
			ans=Math.max(ans, 2*Math.min(inc[i], dec[i])-1);
		}
//		pw.println(Arrays.toString(inc));
//		pw.println(Arrays.toString(dec));
		return ans;
	}
	
	public static boolean reachable(double x1,double y1,double x2,double y2) {
		
		double m=(y2-y1)/(x2-x1);
		double c=y1-x1*m;
		double a=m*m+1;
		double b=2*m*c;
		c=c*c-r*r;
		double sol1=(-b+Math.sqrt(b*b-4*a*c))/(2*a);
		double sol2=(-b-Math.sqrt(b*b-4*a*c))/(2*a);
		
		return Math.abs(x2-x1)-Math.min(Math.abs(sol1-x1), Math.abs(sol2-x1))<0.00000001;
	}	
	
	public static boolean isplus1(int n) {
		return (n-1)%6==0;
	}
	
	public static void permutation(int idx,int v) {
		if(v==(1<<n)-1) {
			perm[x++]=pe.clone();
			return ;
		}
		for (int i = 0; i < n; i++) {
			if((v&1<<i)==0) {
				pe[idx]=aa[i];
				permutation(idx+1, v|1<<i);
			}
		}
		return ;
	}
	
	public static void pre2() {
		for (int i = 0; i < pow.length; i++) {
			long x=1l<<i;
			pow[i]=x+"";
		}
	}
		
	public static void sort(int[]a) {
		mergesort(a, 0, a.length-1);
	}
	
	public static void sortIdx(long[]a,long[]idx) {
		mergesortidx(a, idx, 0, a.length-1);
	}
	
	public static long C(int a,int b) {
		long x=fac[a];
		long y=fac[a-b]*fac[b];
		return x*pow2(y,mod-2)%mod;
	}
	
	public static long pow2(long a,long b) {
		long ans=1;a%=mod;
		for(long i=b;i>0;i/=2) {
			if((i&1)!=0)
				ans=ans*a%mod;
			a=a*a%mod;
		 }    
		    
		 return ans;
	}
	
	public static void pre(){
		fac[0]=1;
		for (int i = 1; i < fac.length; i++) {
			fac[i]=fac[i-1]*i%mod;
		}
		two[0]=1;
		for (int i = 1; i < fac.length; i++) {
			two[i]=two[i-1]*2%mod;
		}
	}
	
	static class Node{
		int x;
		Node next;
		Node previous;
		public Node(int x) {
			this.x=x;
			next=null;
			previous=null;
		}
		@Override
		public String toString() {
			return x+"";
		}
	}
	static class sv{
		public String s;
		public long v;
		public sv(String s,long v) {
			this.s=s;
			this.v=v;
		}
		
	}
	static class LinkedL{
		Node head;
		Node last;
		public LinkedL() {
			head=last=null;
		}
		public void insertLast(int k) {
			Node n=new Node(k);
			n.previous=last;
			last.next=n;
			last=n;
		}
		public void insertFirst(int k) {
			if(head==null) {
				head=last=new Node(k);
			}else {
				Node n=new Node(k);
				n.next=head;
				head.previous=n;
				head=n;
			}
		}
		@Override
		public String toString() {
			String s="";
			Node c=head;
			while(c!=null) {
				s+=c+" ";
				c=c.next;
			}	
			return s;
		}
	}
	public static long p(int n,int k) {
		long res=1;
		if(k<=n/2) {
			while(k-->0) {
				res*=n;
				n--;
			}
		}else {
			res=fac(n)/fac(n-k);
		}
		return res;
	}
	
	public static long eval(String s) {
		long p=1;
		long res=0;
		for (int i = 0; i < s.length(); i++) {
			res+=p*(s.charAt(s.length()-1-i)=='1'?1:0);
			p*=2;
		}
		return res;
	}
	
	public static String binary(long x) {
		String s="";
		while(x!=0) {
			s=(x%2)+s;
			x/=2;
		}
		return s;
	}
	
	public static boolean allSame(String s) {
		char x=s.charAt(0);
		for (int i = 0; i < s.length(); i++) {
			if(s.charAt(i)!=x)return false;
		}
		return true;
	}
	
	public static boolean isPalindrom(String s) {
		int l=0;
		int r=s.length()-1;
		while(l<r) {
			if(s.charAt(r--)!=s.charAt(l++))return false;
			
		}
		return true;
	}
	 
	public static String putAtFront(String s,char c) {
		if(s.length()==0)return s;
		if(s.charAt(s.length()-1)==c) {
			return s.charAt(s.length()-1)+putAtFront(s.substring(0,s.length()-1), c);
		}else {
			return putAtFront(s.substring(0,s.length()-1), c)+s.charAt(s.length()-1);
		}
	}
	
	public static boolean isSubString(String s,String t) {
		int ls=s.length();
		int lt=t.length();
		boolean res=false;
		for (int i = 0; i <=lt-ls; i++) {
			if(t.substring(i, i+ls).equals(s)) {
				res=true;
				break;
			}
		}
		return res;
	}
	
	public static boolean isSorted(int[]a) {
		for (int i = 0; i < a.length-1; i++) {
			if(a[i]>a[i+1])return false;
		}
		return true;
	}
	
	public static boolean isPrime(long n)
    {
 
        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;
 
        // Check if number is 2
        else if (n == 2)
            return true;
 
        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;
 
        // If not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }
	public static long power(long x,long k) {
		long res=1;
		long mod=((int)1e9)+7;
		for (int i = 0; i < k; i++) {
			res*=x;
			res=res%mod;
		}
		return res;
	}
	public static int whichPower(int x) {
		int res=0;
		for (int j = 0; j < 31; j++) {
			if((1<<j&x)!=0) {
				res=j;
				break;
			}
		}
		return res;
	}
 
	public static long evaln(String x,int n) {
		long res=0;
		for (int i = 0; i < x.length(); i++) {
			res+=Long.parseLong(x.charAt(x.length()-1-i)+"")*Math.pow(n, i);
		}
		return res;
	}
	static void merge(int[] arr,int b,int m,int e) {
		int len1=m-b+1,len2=e-m;
		int[] l=new int[len1];
		int[] r=new int[len2];
		for(int i=0;i<len1;i++)l[i]=arr[b+i];
		for(int i=0;i<len2;i++)r[i]=arr[m+1+i];
		int i=0,j=0,k=b;
		while(i<len1 && j<len2) {
			if(l[i]<r[j])arr[k++]=l[i++];
			else arr[k++]=r[j++];
		}
		while(i<len1)arr[k++]=l[i++];
		while(j<len2)arr[k++]=r[j++];
		return;
	}
	static void mergesortidx(long[] arr,long[]idx,int b,int e) {
		if(b<e) {
			int m=b+(e-b)/2;
			mergesortidx(arr,idx,b,m);
			mergesortidx(arr,idx,m+1,e);
			mergeidx(arr,idx,b,m,e);
		}
		return;
		
	}
	static void mergeidx(long[] arr,long[]idx,int b,int m,int e) {
		int len1=m-b+1,len2=e-m;
		long[] l=new long[len1];
		long[] lidx=new long[len1];
		long[] r=new long[len2];
		long[] ridx=new long[len2];
		for(int i=0;i<len1;i++) {
			l[i]=arr[b+i];
			lidx[i]=idx[b+i];
		}
		for(int i=0;i<len2;i++) {
			r[i]=arr[m+1+i];
			ridx[i]=idx[m+1+i];
		}
		int i=0,j=0,k=b;
		while(i<len1 && j<len2) {
			if(l[i]<=r[j]) {
				arr[k++]=l[i++];
				idx[k-1]=lidx[i-1];
			}
			else {
				arr[k++]=r[j++];
				idx[k-1]=ridx[j-1];
			}
		}
		while(i<len1) {
			idx[k]=lidx[i];
			arr[k++]=l[i++];
		}
		while(j<len2) {
			idx[k]=ridx[j];
			arr[k++]=r[j++];
		}
		return;
	}
	static void mergesort(int[] arr,int b,int e) {
		if(b<e) {
			int m=b+(e-b)/2;
			mergesort(arr,b,m);
			mergesort(arr,m+1,e);
			merge(arr,b,m,e);
		}
		return;
		
	}
	
	static long mergen(int[] arr,int b,int m,int e) {
		int len1=m-b+1,len2=e-m;
		int[] l=new int[len1];
		int[] r=new int[len2];
		for(int i=0;i<len1;i++)l[i]=arr[b+i];
		for(int i=0;i<len2;i++)r[i]=arr[m+1+i];
		int i=0,j=0,k=b;
		long c=0;
		while(i<len1 && j<len2) {
			if(l[i]<r[j])arr[k++]=l[i++];
			else {
				arr[k++]=r[j++];
				c=c+(long)(len1-i);
			}
		}
		while(i<len1)arr[k++]=l[i++];
		while(j<len2)arr[k++]=r[j++];
		return c;
	}
	static long mergesortn(int[] arr,int b,int e) {
		long c=0;
		if(b<e) {
			int m=b+(e-b)/2;
			c=c+(long)mergesortn(arr,b,m);
			c=c+(long)mergesortn(arr,m+1,e);
			c=c+(long)mergen(arr,b,m,e);
		}
		return c;
		
	}
	public static long fac(int n) {
		if(n==0)return 1;
		return n*fac(n-1);
	}
	public static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
     
	public static long summ(long x) {
		long sum=0;
		while(x!=0) {
			sum+=x%10;
			x=x/10;
		}
		return sum;
				
	}
	
	public  static ArrayList<Integer> findDivisors(int n){
	        ArrayList<Integer>res=new ArrayList<Integer>();
	        for (int i=1; i<=Math.sqrt(n); i++)
	        {
	            if (n%i==0)
	            {
	                // If divisors are equal, print only one
	                if (n/i == i)
	                	res.add(i);
	                else {
	                	res.add(i);
	                	res.add(n/i);
	                }	
	            }
	        }
	        return res;
	    }

	
	public static void sort2darray(Integer[][]a){
		Arrays.sort(a,Comparator.<Integer[]>comparingInt(x -> x[0]).thenComparingInt(x -> x[1]));
 
	}
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException {
			return br.ready();
		}
		public int[] nextArrint(int size) throws IOException {
			int[] a=new int[size];
			for (int i = 0; i < a.length; i++) {
				a[i]=sc.nextInt();
			}
			return a;
		}
		public long[] nextArrlong(int size) throws IOException {
			long[] a=new long[size];
			for (int i = 0; i < a.length; i++) {
				a[i]=sc.nextLong();
			}
			return a;
		}
		public int[][] next2dArrint(int rows,int columns) throws IOException{
			int[][]a=new int[rows][columns];
			for (int i = 0; i < rows; i++) {
				for (int j = 0; j < columns; j++) {
					a[i][j]=sc.nextInt();
				}
			}
			return a;
		}
		public long[][] next2dArrlong(int rows,int columns) throws IOException{
			long[][]a=new long[rows][columns];
			for (int i = 0; i < rows; i++) {
				for (int j = 0; j < columns; j++) {
					a[i][j]=sc.nextLong();
				}
			}
			return a;
		}
	}
	
	static class Side{
		Point a;
		Point b;
		public Side(Point a,Point b) {
			this.a=a;
			this.b=b;
		}
		@Override
		public boolean equals(Object obj) {
			Side s=(Side)obj;
			return (s.a.equals(a)&&s.b.equals(b))||(s.b.equals(a)&&s.a.equals(b));
		}
		@Override
		public String toString() {
			
			return "("+a.toString()+","+b.toString()+")";
		}
	}
	static class Point{
		int x;
		int y;
		int z;
		public Point(int x,int y,int z) {
			this.x=x;
			this.y=y;
			this.z=z;
		}
		@Override
		public boolean equals(Object obj) {
			Point p=(Point)obj;
			return x==p.x&&y==p.y&&z==p.z;
		}
		@Override
		public String toString() {
			return "("+x+","+y+","+z+")";
		}
	}
	static class Pair{
		long x;
		long y;
		public Pair(long x,long y) {
			this.x=x;
			this.y=y;
		}
		@Override
		public boolean equals(Object obj) {
			Pair p=(Pair)obj;
			return x==p.x&&y==p.y;
		}
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "("+x+","+y+")";
		}
	}
	static class sPair{
		String s;
		Pair p;
		public sPair(String s,Pair p) {
			this.p=p;
			this.s=s;
		}
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return s+" "+p;
		}
	}
	static Scanner sc=new Scanner(System.in);
	static PrintWriter pw=new PrintWriter(System.out);
}