package main

import (
	"bufio"
	"io"
	"os"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c >= '0' && c <= '9' || c == '-' {
			break
		}
		fs.idx++
	}
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return sign * val
}

func writeInt(w *bufio.Writer, x int) {
	if x == 0 {
		w.WriteByte('0')
		w.WriteByte('\n')
		return
	}
	if x < 0 {
		w.WriteByte('-')
		x = -x
	}
	var buf [20]byte
	i := len(buf)
	for x > 0 {
		i--
		buf[i] = byte('0' + x%10)
		x /= 10
	}
	w.Write(buf[i:])
	w.WriteByte('\n')
}

func main() {
	fs := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := fs.NextInt()
	inf := int(^uint(0) >> 1)

	for ; t > 0; t-- {
		n := fs.NextInt()
		m := fs.NextInt()

		grid := make([]byte, n*m)
		for i := 0; i < n; i++ {
			base := i * m
			for j := 0; j < m; j++ {
				if fs.NextInt() != 0 {
					grid[base+j] = 1
				}
			}
		}

		nm := n * m
		dist := make([]int, nm)
		for i := 0; i < nm; i++ {
			dist[i] = -1
		}
		q := make([]int, nm)
		head, tail := 0, 0

		dist[0] = 0
		q[tail] = 0
		tail++

		for head < tail {
			id := q[head]
			head++

			y := id / n
			r := id - y*n
			nd := dist[id] + 1

			r1 := r + 1
			if r1 == n {
				r1 = 0
			}

			if y+1 < m && grid[r1*m+y+1] == 0 {
				nid := (y+1)*n + r1
				if dist[nid] == -1 {
					dist[nid] = nd
					q[tail] = nid
					tail++
				}
			}

			r2 := r + 2
			if r2 >= n {
				r2 -= n
			}
			if grid[r1*m+y] == 0 && grid[r2*m+y] == 0 {
				nid := y*n + r2
				if dist[nid] == -1 {
					dist[nid] = nd
					q[tail] = nid
					tail++
				}
			}
		}

		ans := inf
		base := (m - 1) * n
		goalRow := n - 1

		for r := 0; r < n; r++ {
			d := dist[base+r]
			if d == -1 {
				continue
			}
			rem := (r - (d % n) - goalRow) % n
			if rem < 0 {
				rem += n
			}
			v := d + rem
			if v < ans {
				ans = v
			}
		}

		if ans == inf {
			writeInt(out, -1)
		} else {
			writeInt(out, ans)
		}
	}
}