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

This is a easy version of this problem.The only difference is $$$k=2$$$ 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$$$ indices $$$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,k=2$$$).

Then one line follows, containing $$$n$$$ integers $$$a_1,a_2,\dots,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 2
0 0 0 0
6 2
1 1 0 0 1 1
8 2
1 1 0 1 1 1 1 1
10 2
1 1 0 0 1 1 0 0 0 1
14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
0
3
7
11
12
Note

Test Case $$$1$$$:

You don't need to do any operation.

Test Case $$$2$$$:

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