#include <bits/stdc++.h>
using namespace std;
const int maxN = 2 * 100 * 100 * 100 + 15;
int d[31][31][51];
int solve(int n, int m, int k) {
  if (k == 0) return 0;
  if (n * m < k) return INT_MAX / 3;
  if (m > n) swap(n, m);
  if (d[n][m][k] != -1) return d[n][m][k];
  if (n * m == k) {
    d[n][m][k] = 0;
    return d[n][m][k];
  }
  d[n][m][k] = INT_MAX;
  for (int i = 1; i <= n / 2; i++) {
    for (int j = 0; j <= k; j++) {
      d[n][m][k] =
          min(d[n][m][k], m * m + solve(i, m, j) + solve(n - i, m, k - j));
    }
  }
  for (int i = 1; i <= m / 2; i++) {
    for (int j = 0; j <= k; j++) {
      d[n][m][k] =
          min(d[n][m][k], n * n + solve(n, i, j) + solve(n, m - i, k - j));
    }
  }
  return d[n][m][k];
}
int main() {
  for (int i = 0; i < 31; i++) {
    for (int j = 0; j < 31; j++) {
      for (int k = 0; k < 51; k++) d[i][j][k] = -1;
    }
  }
  int T;
  cin >> T;
  for (int test = 0; test < T; test++) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << solve(n, m, k) << endl;
  }
  return 0;
}
