You are given a garland consisting of n lamps. States of the lamps are represented by the string s of length n. The i-th character of the string s_i equals '0' if the i-th lamp is turned off or '1' if the i-th lamp is turned on. You are also given a positive integer k.

In one move, you can choose one lamp and change its state (i.e. turn it on if it is turned off and vice versa).

The garland is called k-periodic if the distance between each pair of adjacent turned on lamps is exactly k. Consider the case k=3. Then garlands "00010010", "1001001", "00010" and "0" are good but garlands "00101001", "1000001" and "01001100" are not. Note that the garland is not cyclic, i.e. the first turned on lamp is not going after the last turned on lamp and vice versa.

Your task is to find the minimum number of moves you need to make to obtain k-periodic garland from the given one.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 25~ 000) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and k (1 ≤ n ≤ 10^6; 1 ≤ k ≤ n) — the length of s and the required period. The second line of the test case contains the string s consisting of n characters '0' and '1'.

It is guaranteed that the sum of n over all test cases does not exceed 10^6 (∑ n ≤ 10^6).

Output

For each test case, print the answer — the minimum number of moves you need to make to obtain k-periodic garland from the given one.

Example

Input


6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0


Output


1
2
5
4
0
0
import java.io.*; 
import java.math.*;
import java.util.*;
public class KPeriodicGarland {  //~IQEmperor~
	public static void main(String[] args) { 
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int T = I.nextInt();
		while (T-->0) {
			//Find longest periodic chain of period K (Then answer = total ones-longest length)
			int N = I.nextInt();
			int K = I.nextInt();
			String lamps = I.next();
			int ans = 0;
			int ones = 0;
			for (int i = 0; i < N; i++) ones+=lamps.charAt(i)=='1'?1:0;
			ans=ones-1; //Delete all but one lamp (if any)
			ans=max(ans,0);
			for (int cur = 0; cur<K; cur++) { //Overall, chain processing is O(N)
				//since every lamp is visited ONCE
				int curones = 0;
				StringBuilder chain = new StringBuilder();
				for (int next=cur; next<N; next+=K) {
					curones+=lamps.charAt(next)=='1'?1:0;
					chain.append(lamps.charAt(next)); //0s and 1s in current chain
				}
				int curans = ones-curones; //Basically, deleting all other ones that 
				//are not part of the current disjoint chain of lamps
				int len = chain.length();
				int[][] dp = new int[len][3];
				int add = 1001001010; //Minimum moves to have <= 1 sub-array of all 1s in 
				//current chain
				for (int i = 0; i < len; i++) {
					for (int j = 0; j < 3; j++) {
						dp[i][j]=100101010; //unreachable
					}
				}
				if (chain.charAt(0)=='1') dp[0][0]=1; //One move for NO sub-array so far
				else dp[0][0]=0;
				if (chain.charAt(0)=='1') dp[0][1]=0; //No move for sub-array in the making
				else dp[0][1]=0;
				if (chain.charAt(0)=='1') {
					curones--;
					dp[0][2]=curones; //Sub-array of length 1 at start, rest all 0s
					add=min(add,dp[0][2]);
				}else dp[0][2]=curones+1; //Flip first
				for (int i = 1; i < chain.length(); i++) {
					if (chain.charAt(i)=='0') {
						dp[i][0]=dp[i-1][0];
						dp[i][1]=min(dp[i-1][0]+1,dp[i-1][1]+1); //Just starting NOW, or 
						//building upon existing suffix sub-array
						dp[i][2]=min(dp[i-1][1]+curones,dp[i-1][2]); 
						//Stop on going build of previous suffix sub-array (have to kill
						//all future 1s)
						//OR just stay
						//with a previously built sub-array long ago
						
					}else {
						curones--; 
						dp[i][0]=dp[i-1][0]+1; //Have to flip one for all 0s (NO SUB-ARRAY)
						dp[i][1]=min(dp[i-1][0],dp[i-1][1]);
						dp[i][2]=min(dp[i-1][1]+curones+1,dp[i-1][2]);
					}
					add=min(add,dp[i][2]);
				}
				//Check for sub-array that has last ever element as 1 as well
				add=min(add,dp[len-1][1]);
				curans+=add;
				ans=min(ans,curans);
			}
			O.pln(ans);
		}
	}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x, long y) {return Math.abs(x-y);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	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());}
		long nextLong() {return Long.parseLong(next());};
		double nextDouble() {return Double.parseDouble(next());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}


