```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func solve() {
	var n, k int
	fmt.Fscan(in, &n, &k)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &a[i])
	}

	// Strategy:
	// 1. Identify and convert 1s to 0s as they are most problematic.
	//    We prioritize 1s that give the most immediate reduction in sadness.
	// 2. If k remains and all 1s are gone, treat the problem as breaking bad segments 
	//    of (Odd, Odd), (Odd, Even), etc. using Vertex Cover logic on paths.

	// Identify indices of 1s
	onesIndices := make([]int, 0)
	for i, v := range a {
		if v == 1 {
			onesIndices = append(onesIndices, i)
		}
	}

	// If we can't convert all 1s, we act greedily based on gain
	// Gain = (current bad neighbors) - (future bad neighbors)
	// Current bad neighbors for 1 are neighbors with gcd=1 (which is all neighbors since gcd(1,x)=1)
	// Future bad neighbors for 0 are neighbors equal to 1.
	if len(onesIndices) > k {
		// Calculate gain for each 1
		type One struct {
			idx  int
			gain int
		}
		gains := make([]One, len(onesIndices))
		for j, idx := range onesIndices {
			currentBad := 0
			if idx > 0 {
				currentBad++ // gcd(1, left) is always 1
			}
			if idx < n-1 {
				currentBad++ // gcd(1, right) is always 1
			}

			futureBad := 0
			if idx > 0 && a[idx-1] == 1 {
				futureBad++
			}
			if idx < n-1 && a[idx+1] == 1 {
				futureBad++
			}
			gains[j] = One{idx, currentBad - futureBad}
		}

		// Sort by gain descending
		sort.Slice(gains, func(i, j int) bool {
			return gains[i].gain > gains[j].gain
		})

		// Convert top k
		for i := 0; i < k; i++ {
			a[gains[i].idx] = 0
		}
		k = 0
	} else {
		// Convert all 1s
		for _, idx := range onesIndices {
			a[idx] = 0
		}
		k -= len(onesIndices)
	}

	// If k is 0, just compute sadness and return
	if k == 0 {
		sadness := 0
		for i := 0; i < n-1; i++ {
			if gcd(a[i], a[i+1]) == 1 {
				sadness++
			}
		}
		fmt.Fprintln(out, sadness)
		return
	}

	// Phase 2: No 1s remain (or we used all k).
	// If we are here, there are no 1s in array.
	// Bad pairs are those with gcd(a[i], a[i+1]) == 1.
	// Since no 1s, and 0s are good with everything (gcd(0, x) = x > 1),
	// bad pairs form segments of non-zero numbers.
	// Graph of bad edges is a collection of disjoint paths.
	// We want to remove edges by converting nodes to 0 (cost 1 per node).
	// Each segment of E edges provides floor(E/2) moves of gain 2, and (E%2) moves of gain 1.

	badEdges := make([]bool, n-1)
	totalBad := 0
	for i := 0; i < n-1; i++ {
		if gcd(a[i], a[i+1]) == 1 {
			badEdges[i] = true
			totalBad++
		}
	}

	// Collect segment lengths (number of edges)
	var segments []int
	currentLen := 0
	for i := 0; i < n-1; i++ {
		if badEdges[i] {
			currentLen++
		} else {
			if currentLen > 0 {
				segments = append(segments, currentLen)
			}
			currentLen = 0
		}
	}
	if currentLen > 0 {
		segments = append(segments, currentLen)
	}

	// Calculate potential reductions
	gain2 := 0
	gain1 := 0
	for _, length := range segments {
		gain2 += length / 2
		gain1 += length % 2
	}

	reduction := 0
	// Apply k for gain 2
	canTake := min(k, gain2)
	reduction += canTake * 2
	k -= canTake

	// Apply k for gain 1
	if k > 0 {
		canTake = min(k, gain1)
		reduction += canTake * 1
		k -= canTake
	}

	// Note: if k is still > 0, we can break more "internal" structures but max possible reduction 
	// is totalBad. The logic above covers max independent edges.
	// Wait, actually, on a path of length E, we can remove ALL edges if k is large enough.
	// The formula above accounts for E edges: (E/2)*2 + (E%2)*1 = E.
	// So reduction is capped correctly at total edges of the segment.
	
	fmt.Fprintln(out, totalBad-reduction)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

var in *bufio.Reader
var out *bufio.Writer

func main() {
	in = bufio.NewReader(os.Stdin)
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for i := 0; i < t; i++ {
		solve()
	}
}
```