package main

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

const (
	MaxN = 30
	MaxK = 50
	INF  = int(1e9)
)

func main() {
	var dp [MaxN + 1][MaxN + 1][MaxK + 1]int

	for n := 0; n <= MaxN; n++ {
		for m := 0; m <= MaxN; m++ {
			for k := 0; k <= MaxK; k++ {
				dp[n][m][k] = INF
			}
			dp[n][m][0] = 0
			area := n * m
			if area <= MaxK {
				dp[n][m][area] = 0
			}
		}
	}

	for n := 1; n <= MaxN; n++ {
		for m := 1; m <= MaxN; m++ {
			area := n * m
			limit := MaxK
			if area < limit {
				limit = area
			}
			for k := 1; k <= limit; k++ {
				if k == area {
					dp[n][m][k] = 0
					continue
				}
				best := dp[n][m][k]

				for i := 1; i <= n/2; i++ {
					cost := m * m
					a1 := i * m
					a2 := (n - i) * m
					low := 0
					if k-a2 > low {
						low = k - a2
					}
					high := k
					if a1 < high {
						high = a1
					}
					for x := low; x <= high; x++ {
						v := dp[i][m][x] + dp[n-i][m][k-x] + cost
						if v < best {
							best = v
						}
					}
				}

				for j := 1; j <= m/2; j++ {
					cost := n * n
					a1 := n * j
					a2 := n * (m - j)
					low := 0
					if k-a2 > low {
						low = k - a2
					}
					high := k
					if a1 < high {
						high = a1
					}
					for x := low; x <= high; x++ {
						v := dp[n][j][x] + dp[n][m-j][k-x] + cost
						if v < best {
							best = v
						}
					}
				}

				dp[n][m][k] = best
			}
		}
	}

	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for ; t > 0; t-- {
		var n, m, k int
		fmt.Fscan(in, &n, &m, &k)
		fmt.Fprintln(out, dp[n][m][k])
	}
}