package main

import (
	"bufio"
	"io"
	"os"
	"sort"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
}

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

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

type Pair struct {
	c   int
	cnt int
}

type Item struct {
	val   int64
	color int
}

func heapPush(h []Item, x Item) []Item {
	h = append(h, x)
	i := len(h) - 1
	for i > 0 {
		p := (i - 1) >> 1
		if h[p].val >= h[i].val {
			break
		}
		h[p], h[i] = h[i], h[p]
		i = p
	}
	return h
}

func heapPop(h []Item) []Item {
	n := len(h) - 1
	if n == 0 {
		return h[:0]
	}
	h[0] = h[n]
	h = h[:n]
	i := 0
	for {
		l := i*2 + 1
		if l >= n {
			break
		}
		r := l + 1
		j := l
		if r < n && h[r].val > h[l].val {
			j = r
		}
		if h[i].val >= h[j].val {
			break
		}
		h[i], h[j] = h[j], h[i]
		i = j
	}
	return h
}

func main() {
	fs := NewFastScanner()
	t := fs.NextInt()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	buf := make([]byte, 0, 32)

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

		counts := make([][]Pair, n)
		blanks := make([]int64, n)

		for i := 0; i < n; i++ {
			vals := make([]int, 0, m)
			var b int64
			for j := 0; j < m; j++ {
				x := fs.NextInt()
				if x == -1 {
					b++
				} else {
					vals = append(vals, x)
				}
			}
			blanks[i] = b
			if len(vals) == 0 {
				continue
			}
			sort.Ints(vals)
			pairs := make([]Pair, 0, len(vals))
			cur := vals[0]
			cnt := 1
			for j := 1; j < len(vals); j++ {
				if vals[j] == cur {
					cnt++
				} else {
					pairs = append(pairs, Pair{c: cur, cnt: cnt})
					cur = vals[j]
					cnt = 1
				}
			}
			pairs = append(pairs, Pair{c: cur, cnt: cnt})
			counts[i] = pairs
		}

		var base int64
		for i := 0; i+1 < n; i++ {
			a := counts[i]
			b := counts[i+1]
			p, q := 0, 0
			for p < len(a) && q < len(b) {
				if a[p].c == b[q].c {
					base += int64(a[p].cnt) * int64(b[q].cnt)
					p++
					q++
				} else if a[p].c < b[q].c {
					p++
				} else {
					q++
				}
			}
		}

		raw := make([]int64, k+1)
		h := make([]Item, 0)
		var lazy int64
		var d int64

		currentMax := func() int64 {
			for len(h) > 0 {
				top := h[0]
				if raw[top.color] != top.val || top.val <= lazy {
					h = heapPop(h)
					continue
				}
				return top.val - lazy
			}
			return 0
		}

		addColor := func(c int, inc int64) {
			cur := raw[c]
			if cur < lazy {
				cur = lazy
			}
			cur += inc
			raw[c] = cur
			h = heapPush(h, Item{val: cur, color: c})
		}

		addUnary := func(i int) {
			r := blanks[i]
			if r == 0 {
				return
			}
			if i > 0 {
				for _, p := range counts[i-1] {
					addColor(p.c, r*int64(p.cnt))
				}
			}
			if i+1 < n {
				for _, p := range counts[i+1] {
					addColor(p.c, r*int64(p.cnt))
				}
			}
		}

		addUnary(0)
		for i := 1; i < n; i++ {
			mx := currentMax()
			b := blanks[i-1] * blanks[i]
			if mx > b {
				d += mx
				lazy += mx - b
			} else {
				d += b
			}
			addUnary(i)
		}

		ans := base + d + currentMax()
		buf = strconv.AppendInt(buf[:0], ans, 10)
		out.Write(buf)
		out.WriteByte('\n')
	}

	out.Flush()
}