#include <bits/stdc++.h>
using namespace std;
int n, m, k, T, d[35][35][55];
int f(int p, int q, int w) {
  int i, j, mn = 1e9;
  if (w == 0 || p * q == w) return 0;
  if (d[p][q][w] != -1) return d[p][q][w];
  for (i = 1; i <= p / 2; i++) {
    for (j = 0; j <= w; j++) {
      mn = min(mn, f(i, q, j) + f(p - i, q, w - j) + q * q);
    }
  }
  for (i = 1; i <= q / 2; i++) {
    for (j = 0; j <= w; j++) {
      mn = min(mn, f(p, i, j) + f(p, q - i, w - j) + p * p);
    }
  }
  return d[p][q][w] = mn;
}
int main() {
  int i, j;
  cin >> T;
  memset(d, -1, sizeof(d));
  while (T--) {
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", f(n, m, k));
  }
  return 0;
}
