#include <bits/stdc++.h>
using namespace std;
int memo[50][50][60];
int f(int n, int m, int k) {
  if (n * m < k) return 1 << 28;
  if (memo[n][m][k]) return memo[n][m][k];
  if (k == 0 || n * m == k) return 0;
  if (n == 1 || m == 1) return 1;
  int ans = 1 << 30;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j <= k; j++) {
      ans = min(ans, f(i, m, j) + f(n - i, m, k - j) + m * m);
    }
  }
  for (int i = 1; i < m; i++) {
    for (int j = 0; j <= k; j++) {
      ans = min(ans, f(i, n, j) + f(m - i, n, k - j) + n * n);
    }
  }
  return memo[n][m][k] = ans;
}
int main() {
  int t, n, m, k;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &n, &m, &k);
    printf("%d\n", f(n, m, k));
  }
}
