package main

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

type Point struct {
	u, v int
}

func minPaths(pts []Point) int {
	if len(pts) == 0 {
		return 0
	}
	
	sort.Slice(pts, func(i, j int) bool {
		if pts[i].u != pts[j].u {
			return pts[i].u < pts[j].u
		}
		return pts[i].v < pts[j].v
	})

	tails := make([]int, 0)
	for _, p := range pts {
		x := -p.v
		l, r := 0, len(tails)
		for l < r {
			m := l + (r-l)/2
			if tails[m] < x {
				l = m + 1
			} else {
				r = m
			}
		}
		if l == len(tails) {
			tails = append(tails, x)
		} else {
			tails[l] = x
		}
	}
	return len(tails)
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, 10*1024*1024)

	scanInt := func() int {
		scanner.Scan()
		res := 0
		for _, b := range scanner.Bytes() {
			res = res*10 + int(b-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}
	t := 0
	for _, b := range scanner.Bytes() {
		t = t*10 + int(b-'0')
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	evenPts := make([]Point, 0, 1024)
	oddPts := make([]Point, 0, 1024)

	for tc := 0; tc < t; tc++ {
		n := scanInt()
		m := scanInt()
		evenPts = evenPts[:0]
		oddPts = oddPts[:0]
		
		for i := 1; i <= n; i++ {
			scanner.Scan()
			s := scanner.Bytes()
			for j := 1; j <= m; j++ {
				if s[j-1] == '1' {
					u := i + j
					v := i - j
					if u%2 == 0 {
						evenPts = append(evenPts, Point{u, v})
					} else {
						oddPts = append(oddPts, Point{u, v})
					}
				}
			}
		}
		
		ans := minPaths(evenPts) + minPaths(oddPts)
		fmt.Fprintln(out, ans)
	}
}