E2. Magic Xor(Hard Version)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is a hard version of this problem.The only difference is $$$2 \leq k \leq 50$$$ in this version.

You are given a binary array $$$a$$$ of size $$$n$$$ consisting of $$$0$$$ or $$$1$$$.

You can do the following operation any number of times:

  • choose an index $$$i$$$ ($$$1 \lt i \lt n$$$);
  • change $$$a_{i-1}$$$ to $$$a_{i-1}\oplus a_i$$$ and change $$$a_{i+1}$$$ to $$$a_{i+1}\oplus a_i$$$. (Here $$$\oplus$$$ donates the bitwise XOR).

Your goal is to make $$$a$$$ satisfy the following condition:

  • there are at most $$$k$$$ index $$$i(1\leq i \leq n)$$$ satisfying $$$a_i=1$$$.

Find the minimum number of operations you need. It can be proven that your goal is always able to be realized.

Input

The first line of the input contains a single integer $$$t$$$($$$1\le t\le 10^5$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n,k$$$($$$4\le n\le 5\cdot 10^5$$$,$$$2\leq k \leq 50$$$).

Then one line follows, containing $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$($$$0\le a_i\le 1$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output a single line — the minimum number of operations.

Example
Input
5
4 50
1 1 1 1
7 4
1 1 0 1 1 1 1
8 3
1 1 0 1 1 1 1 1
10 2
1 1 1 1 1 1 0 0 0 1
14 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
0
1
3
15
6
Note

Test Case $$$1$$$:

You don't need to do any operation.

Test Case $$$2$$$:

You only need to choose $$$i=5$$$. After your operation,$$$a=[1,1,0,0,1,0,1]$$$.

Test Case $$$3$$$:

  1. You choose $$$i=5$$$. After your operation,$$$a=[1,1,0,0,1,0,1,1]$$$;
  2. You choose $$$i=7$$$. After your operation,$$$a=[1,1,0,0,1,1,1,0]$$$;
  3. You choose $$$i=6$$$. After your operation,$$$a=[1,1,0,0,0,1,0,0]$$$.