package main

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

type State struct {
	w, d, r, c int
}

type MinHeap []State

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

type Dist struct {
	w, d int
}

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

	var t int
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}

	for tc := 0; tc < t; tc++ {
		var n, k int
		fmt.Fscan(in, &n, &k)

		vert := make([][]int, k+1)
		horiz := make([][]int, k+1)
		for i := 0; i <= k; i++ {
			vert[i] = make([]int, k+1)
			horiz[i] = make([]int, k+1)
		}

		for i := 0; i < n; i++ {
			var r1, c1, r2, c2 int
			fmt.Fscan(in, &r1, &c1, &r2, &c2)
			if r1 == r2 {
				cmin := c1
				if c2 < c1 {
					cmin = c2
				}
				vert[r1][cmin]++
			} else if c1 == c2 {
				rmin := r1
				if r2 < r1 {
					rmin = r2
				}
				horiz[rmin][c1]++
			}
		}

		wVert := make([][]int, k+1)
		wHoriz := make([][]int, k+1)
		for i := 0; i <= k; i++ {
			wVert[i] = make([]int, k+1)
			wHoriz[i] = make([]int, k+1)
		}

		for r := 1; r <= k; r++ {
			for c := 1; c < k; c++ {
				wVert[r][c] = vert[r][c] + vert[k-r+1][k-c]
			}
		}
		for r := 1; r < k; r++ {
			for c := 1; c <= k; c++ {
				wHoriz[r][c] = horiz[r][c] + horiz[k-r][k-c+1]
			}
		}

		dist := make([][]Dist, k+1)
		const INF = int(1e9)
		for i := 0; i <= k; i++ {
			dist[i] = make([]Dist, k+1)
			for j := 0; j <= k; j++ {
				dist[i][j] = Dist{w: INF, d: INF}
			}
		}

		sr, sc := k/2, k/2
		dist[sr][sc] = Dist{w: 0, d: 0}
		h := &MinHeap{}
		heap.Init(h)
		heap.Push(h, State{w: 0, d: 0, r: sr, c: sc})

		minCut := INF

		for h.Len() > 0 {
			st := heap.Pop(h).(State)

			if st.w > dist[st.r][st.c].w || (st.w == dist[st.r][st.c].w && st.d > dist[st.r][st.c].d) {
				continue
			}

			if st.r == 0 || st.r == k || st.c == 0 || st.c == k {
				minCut = st.w
				break
			}

			if st.r > 0 {
				nr, nc := st.r-1, st.c
				weight := wVert[st.r][st.c]
				nw, nd := st.w+weight, st.d+1
				if nw < dist[nr][nc].w || (nw == dist[nr][nc].w && nd < dist[nr][nc].d) {
					dist[nr][nc] = Dist{w: nw, d: nd}
					heap.Push(h, State{w: nw, d: nd, r: nr, c: nc})
				}
			}
			if st.r < k {
				nr, nc := st.r+1, st.c
				weight := wVert[st.r+1][st.c]
				nw, nd := st.w+weight, st.d+1
				if nw < dist[nr][nc].w || (nw == dist[nr][nc].w && nd < dist[nr][nc].d) {
					dist[nr][nc] = Dist{w: nw, d: nd}
					heap.Push(h, State{w: nw, d: nd, r: nr, c: nc})
				}
			}
			if st.c > 0 {
				nr, nc := st.r, st.c-1
				weight := wHoriz[st.r][st.c]
				nw, nd := st.w+weight, st.d+1
				if nw < dist[nr][nc].w || (nw == dist[nr][nc].w && nd < dist[nr][nc].d) {
					dist[nr][nc] = Dist{w: nw, d: nd}
					heap.Push(h, State{w: nw, d: nd, r: nr, c: nc})
				}
			}
			if st.c < k {
				nr, nc := st.r, st.c+1
				weight := wHoriz[st.r][st.c+1]
				nw, nd := st.w+weight, st.d+1
				if nw < dist[nr][nc].w || (nw == dist[nr][nc].w && nd < dist[nr][nc].d) {
					dist[nr][nc] = Dist{w: nw, d: nd}
					heap.Push(h, State{w: nw, d: nd, r: nr, c: nc})
				}
			}
		}

		fmt.Fprintln(out, n-minCut)
	}
}