```go
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

type State struct {
	d, r, c int
}

type PQ []*State

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].d < pq[j].d }
func (pq PQ) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) {
	*pq = append(*pq, x.(*State))
}
func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func canonical(r, c, k int) (int, int) {
	if r > k/2 {
		return k - r, k - c
	}
	if r == k/2 && c > k/2 {
		return k - r, k - c
	}
	return r, c
}

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

func main() {
	reader := bufio.NewReader(os.Stdin)

	nextInt := func() int {
		var n int
		var c byte
		var err error
		for {
			c, err = reader.ReadByte()
			if err != nil {
				return 0
			}
			if (c >= '0' && c <= '9') || c == '-' {
				break
			}
		}
		sign := 1
		if c == '-' {
			sign = -1
		} else {
			n = int(c - '0')
		}
		for {
			c, err = reader.ReadByte()
			if err != nil || c < '0' || c > '9' {
				break
			}
			n = n*10 + int(c-'0')
		}
		return n * sign
	}

	t := nextInt()
	for tc := 0; tc < t; tc++ {
		n := nextInt()
		k := nextInt()

		costH := make([][]int, k+1)
		for i := range costH {
			costH[i] = make([]int, k)
		}

		costV := make([][]int, k)
		for i := range costV {
			costV[i] = make([]int, k+1)
		}

		for i := 0; i < n; i++ {
			r1, c1, r2, c2 := nextInt(), nextInt(), nextInt(), nextInt()
			if r1 == r2 {
				c := min(c1, c2)
				costV[r1-1][c]++
			} else {
				r := min(r1, r2)
				costH[r][c1-1]++
			}
		}

		dist := make([][]int, k/2+1)
		for i := range dist {
			dist[i] = make([]int, k+1)
			for j := range dist[i] {
				dist[i][j] = -1
			}
		}

		pq := &PQ{}
		heap.Init(pq)

		startR, startC := k/2, k/2
		dist[startR][startC] = 0
		heap.Push(pq, &State{0, startR, startC})

		minCut := -1

		for pq.Len() > 0 {
			curr := heap.Pop(pq).(*State)
			d, r, c := curr.d, curr.r, curr.c

			if dist[r][c] < d {
				continue
			}

			if r == 0 || c == 0 || c == k {
				minCut = d
				break
			}

			if c < k {
				w := costH[r][c] + costH[k-r][k-c-1]
				canR, canC := canonical(r, c+1, k)
				if dist[canR][canC] == -1 || dist[canR][canC] > d+w {
					dist[canR][canC] = d + w
					heap.Push(pq, &State{d + w, canR, canC})
				}
			}

			if c > 0 {
				w := costH[r][c-1] + costH[k-r][k-c]
				canR, canC := canonical(r, c-1, k)
				if dist[canR][canC] == -1 || dist[canR][canC] > d+w {
					dist[canR][canC] = d + w
					heap.Push(pq, &State{d + w, canR, canC})
				}
			}

			if r < k {
				w := costV[r][c] + costV[k-r-1][k-c]
				canR, canC := canonical(r+1, c, k)
				if dist[canR][canC] == -1 || dist[canR][canC] > d+w {
					dist[canR][canC] = d + w
					heap.Push(pq, &State{d + w, canR, canC})
				}
			}

			if r > 0 {
				w := costV[r-1][c] + costV[k-r][k-c]
				canR, canC := canonical(r-1, c, k)
				if dist[canR][canC] == -1 || dist[canR][canC] > d+w {
					dist[canR][canC] = d + w
					heap.Push(pq, &State{d + w, canR, canC})
				}
			}
		}

		fmt.Println(n - minCut)
	}
}
```