#include <bits/stdc++.h>
using namespace std;
int DP[32][32][60];
int dp(int n, int m, int k) {
  if (n * m == k || k == 0) return 0;
  if (n * m < k) return 1e8;
  if (DP[n][m][k] != -1) return DP[n][m][k];
  int res = 1e8;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < m; j++) {
      res = min(res, m * m + dp(i, m, j) + dp(n - i, m, k - j));
    }
  }
  swap(n, m);
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < m; j++) {
      res = min(res, m * m + dp(i, m, j) + dp(n - i, m, k - j));
    }
  }
  swap(n, m);
  return DP[n][m][k] = res;
}
int main() {
  int t;
  scanf("%d", &t);
  memset(DP, -1, sizeof DP);
  while (t--) {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", dp(n, m, k));
  }
  return 0;
}
