#include <bits/stdc++.h>
int cache[31][31][51];
int min(int a, int b) { return a < b ? a : b; }
int ans(int n, int m, int k) {
  int &ret = cache[n][m][k];
  if (ret != -1) return ret;
  if (k > n * m) return 100000;
  if (k == 0 || k == n * m) return 0;
  ret = 100000;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j <= k; j++) {
      ret = min(ret, m * m + ans(i, m, j) + ans(n - i, m, k - j));
    }
  }
  for (int i = 1; i < m; i++) {
    for (int j = 0; j <= k; j++) {
      ret = min(ret, n * n + ans(n, i, j) + ans(n, m - i, k - j));
    }
  }
  return ret;
}
int main() {
  int t;
  int n, m, k;
  scanf("%d", &t);
  memset(cache, -1, sizeof(cache));
  while (t--) {
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", ans(n, m, k));
  }
}
