#include <bits/stdc++.h>
using namespace std;
int buf[20];
int read() {
  int x = 0;
  char ch = getchar();
  bool f = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
void write(int x) {
  if (!x) {
    putchar(48);
    return;
  }
  int l = 0;
  if (x < 0) putchar('-'), x = -x;
  while (x) buf[++l] = x % 10, x = x / 10;
  while (l) putchar(buf[l--] + 48);
}
const int maxn = 35;
int squa[maxn], dp[maxn][maxn][55];
void pre() {
  for (int i = 1; i < 31; ++i) squa[i] = i * i;
}
int solve(int r, int c, int k) {
  if (dp[r][c][k] || k == r * c || k == 0) return dp[r][c][k];
  int ret = 100000007;
  for (int i = 1; i < (r >> 1) + 1; ++i)
    for (int j = 0; j < k + 1; ++j)
      ret = min(ret, squa[c] + solve(i, c, j) + solve(r - i, c, k - j));
  for (int i = 1; i < (c >> 1) + 1; ++i)
    for (int j = 0; j < k + 1; ++j)
      ret = min(ret, squa[r] + solve(r, i, j) + solve(r, c - i, k - j));
  return dp[r][c][k] = ret;
}
int main() {
  int t = read();
  pre();
  while (t--) {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    printf("%d\n", solve(n, m, k));
  }
  return 0;
}
