package main
import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"os"
	"strings"
)
type FastReader struct {
	r   *bufio.Reader
	buf []byte
	pos int
}
func NewFastReader() *FastReader {
	return &FastReader{
		r: bufio.NewReaderSize(os.Stdin, 1<<20),
	}
}
func (fr *FastReader) readByte() (byte, error) {
	if fr.pos >= len(fr.buf) {
		var err error
		fr.buf, err = fr.r.ReadBytes('\n')
		if err != nil && len(fr.buf) == 0 {
			return 0, err
		}
		fr.pos = 0
	}
	b := fr.buf[fr.pos]
	fr.pos++
	return b, nil
}
func (fr *FastReader) readInt() (int64, error) {
	sign := int64(1)
	var x int64
	for {
		b, err := fr.readByte()
		if err != nil {
			return 0, err
		}
		if b == '-' {
			sign = -1
			break
		}
		if b >= '0' && b <= '9' {
			x = int64(b - '0')
			break
		}
	}
	for {
		b, err := fr.readByte()
		if err != nil || b < '0' || b > '9' {
			break
		}
		x = x*10 + int64(b-'0')
	}
	return sign * x, nil
}
func (fr *FastReader) readString(n int) (string, error) {
	res := make([]byte, n)
	i := 0
	for i < n {
		b, err := fr.readByte()
		if err != nil {
			return "", err
		}
		if b == '\n' || b == ' ' || b == '\r' {
			continue
		}
		res[i] = b
		i++
	}
	return string(res), nil
}
func (fr *FastReader) readLine() (string, error) {
	line, err := fr.r.ReadString('\n')
	return strings.TrimRight(line, "\r\n"), err
}
func readLine(fr *FastReader) (string, error) {
	return fr.readLine()
}
func readUint64(fr *FastReader) (uint64, error) {
	x, err := fr.readInt()
	return uint64(x), err
}
func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}
const (
	intinf    = math.MaxInt32
	intinfinf = math.MaxInt64
)
type prq []*pqitems
func (pq prq) Len() int           { return len(pq) }
func (pq prq) Less(i, j int) bool { return pq[i].currmaxso < pq[j].currmaxso }
func (pq prq) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *prq) Push(x interface{}) {
	*pq = append(*pq, x.(*pqitems))
}
func (pq *prq) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}
var (
	ndim, tarrr int
	kbudget     int64
	amat        [][]int
	cmat        [][]byte
	smmat       [][]bool
	di          = []int{-1, 0, 1, 0}
	dj          = []int{0, -1, 0, 1}
)
type bfsstte struct{ r, c int }
func poss(si, sj, ti, tj, thre int) bool {
	if amat[si][sj] > thre {
		return false
	}
	reached := make([][]bool, ndim)
	for i := range reached {
		reached[i] = make([]bool, ndim)
	}
	q := []bfsstte{{si, sj}}
	reached[si][sj] = true
	for head := 0; head < len(q); head++ {
		u := q[head]
		if u.r == ti && u.c == tj {
			return true
		}
		for d := 0; d < 4; d++ {
			ni, nj := u.r+di[d], u.c+dj[d]
			if ni >= 0 && ni < ndim && nj >= 0 && nj < ndim && !reached[ni][nj] && amat[ni][nj] <= thre {
				reached[ni][nj] = true
				q = append(q, bfsstte{ni, nj})
			}
		}
	}
	return false
}
type edger struct {
	to, rev int
	cap     int64
}
var (
	network [][]edger
	lvld    []int
	ptrd    []int
)
func addedged(u, v int, c int64) {
	network[u] = append(network[u], edger{v, len(network[v]), c})
	network[v] = append(network[v], edger{u, len(network[u]) - 1, 0})
}
func bfsd(s, t int) bool {
	lvld = make([]int, len(network))
	for i := range lvld {
		lvld[i] = -1
	}
	q := []int{s}
	lvld[s] = 0
	for head := 0; head < len(q); head++ {
		u := q[head]
		for _, e := range network[u] {
			if e.cap > 0 && lvld[e.to] < 0 {
				lvld[e.to] = lvld[u] + 1
				q = append(q, e.to)
			}
		}
	}
	return lvld[t] >= 0
}
func dfsd(u, t int, f int64) int64 {
	if u == t {
		return f
	}
	for ptrd[u] < len(network[u]) {
		i := ptrd[u]
		e := &network[u][i]
		if e.cap > 0 && lvld[u] < lvld[e.to] {
			pushed := dfsd(e.to, t, minInt64(f, e.cap))
			if pushed > 0 {
				e.cap -= pushed
				network[e.to][e.rev].cap += pushed
				return pushed
			}
		}
		ptrd[u]++
	}
	return 0
}
func dinic(s, t int) int64 {
	flow := int64(0)
	for bfsd(s, t) {
		ptrd = make([]int, len(network))
		for {
			pushed := dfsd(s, t, intinfinf)
			if pushed == 0 {
				break
			}
			flow += pushed
		}
	}
	return flow
}
func canposs(mid int64) bool {
	if int64(amat[ndim-1][0]) >= mid || int64(amat[tarrr-1][ndim-1]) >= mid {
		return true
	}
	ttl := ndim * ndim
	network = make([][]edger, 2*ttl)
	src := (ndim-1)*ndim + 0
	sink := ttl + (tarrr-1)*ndim + (ndim - 1)
	for i := 0; i < ndim; i++ {
		for j := 0; j < ndim; j++ {
			if int64(amat[i][j]) >= mid {
				continue
			}
			in := i*ndim + j
			out := in + ttl
			var cap int64 = intinfinf
			if cmat[i][j] == '1' && !smmat[i][j] {
				cap = mid - int64(amat[i][j])
			}
			addedged(in, out, cap)
			for d := 0; d < 4; d++ {
				ni, nj := i+di[d], j+dj[d]
				if ni >= 0 && ni < ndim && nj >= 0 && nj < ndim && int64(amat[ni][nj]) < mid {
					addedged(out, ni*ndim+nj, intinfinf)
				}
			}
		}
	}
	return dinic(src, sink) <= kbudget
}
type pqitems struct {
	currmaxso, r, c int
}
func solve(fr *FastReader, writer *bufio.Writer) error {
	tmp, _ := fr.readInt()
	ndim = int(tmp)
	tmp, _ = fr.readInt()
	tarrr = int(tmp)
	kbudget, _ = fr.readInt()
	amat = make([][]int, ndim)
	for i := range amat {
		amat[i] = make([]int, ndim)
		for j := range amat[i] {
			tmp, _ = fr.readInt()
			amat[i][j] = int(tmp)
		}
	}
	cmat = make([][]byte, ndim)
	for i := 0; i < ndim; i++ {
		s, _ := fr.readString(ndim)
		cmat[i] = []byte(s)
	}
	low, high := 0, 1_000_000
	dsm := high + 1
	for low <= high {
		mid := (low + high) / 2
		if poss(0, 0, tarrr-1, ndim-1, mid) {
			dsm = mid
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	smmat = make([][]bool, ndim)
	for i := range smmat {
		smmat[i] = make([]bool, ndim)
	}
	maxst := make([][]int, ndim)
	for i := range maxst {
		maxst[i] = make([]int, ndim)
		for j := range maxst[i] {
			maxst[i][j] = intinf
		}
	}
	p := &prq{}
	heap.Init(p)
	maxst[0][0] = amat[0][0]
	heap.Push(p, &pqitems{amat[0][0], 0, 0})
	for p.Len() > 0 {
		cur := heap.Pop(p).(*pqitems)
		if cur.currmaxso > maxst[cur.r][cur.c] {
			continue
		}
		for d := 0; d < 4; d++ {
			ni, nj := cur.r+di[d], cur.c+dj[d]
			if ni >= 0 && ni < ndim && nj >= 0 && nj < ndim {
				nm := maxInt(cur.currmaxso, amat[ni][nj])
				if nm < maxst[ni][nj] {
					maxst[ni][nj] = nm
					heap.Push(p, &pqitems{nm, ni, nj})
				}
			}
		}
	}
	maxend := make([][]int, ndim)
	for i := range maxend {
		maxend[i] = make([]int, ndim)
		for j := range maxend[i] {
			maxend[i][j] = intinf
		}
	}
	*p = prq{}
	heap.Init(p)
	tr, tc := tarrr-1, ndim-1
	maxend[tr][tc] = amat[tr][tc]
	heap.Push(p, &pqitems{amat[tr][tc], tr, tc})
	for p.Len() > 0 {
		cur := heap.Pop(p).(*pqitems)
		if cur.currmaxso > maxend[cur.r][cur.c] {
			continue
		}
		for d := 0; d < 4; d++ {
			ni, nj := cur.r+di[d], cur.c+dj[d]
			if ni >= 0 && ni < ndim && nj >= 0 && nj < ndim {
				nm := maxInt(cur.currmaxso, amat[ni][nj])
				if nm < maxend[ni][nj] {
					maxend[ni][nj] = nm
					heap.Push(p, &pqitems{nm, ni, nj})
				}
			}
		}
	}
	for i := 0; i < ndim; i++ {
		for j := 0; j < ndim; j++ {
			smmat[i][j] = (maxst[i][j] == dsm && maxend[i][j] == dsm)
		}
	}
	lwf, hff := int64(0), int64(1_000_000)+kbudget
	var dsf int64
	for lwf <= hff {
		mid := (lwf + hff + 1) / 2
		if canposs(mid) {
			dsf = mid
			lwf = mid + 1
		} else {
			hff = mid - 1
		}
	}
	fmt.Println(dsm, dsf)
	return nil
}
func main() {
	fr := NewFastReader()
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	tt, _ := fr.readInt()
	t := int(tt)
	for i := 0; i < t; i++ {
		if err := solve(fr, writer); err != nil {
			panic(err)
		}
	}
}