#include <bits/stdc++.h>
using namespace std;
int dp[100][100][100];
int solve(int n, int m, int k) {
  if (k == 0) return 0;
  int &ret = dp[n][m][k];
  if (ret != -1) return ret;
  int x1 = 1e9, x2 = 1e9, x3 = 1e9, x4 = 1e9;
  if (n * m == k) return solve(0, 0, 0);
  for (int i = 1; i <= n; i++) {
    x1 = min(x1, m * m + solve(n - i, m, k));
    if (i * m <= k) x3 = min(x3, m * m + solve(n - i, m, k - i * m));
  }
  for (int i = 1; i <= m; i++) {
    x2 = min(x2, n * n + solve(n, m - i, k));
    if (i * n <= k) x4 = min(x4, n * n + solve(n, m - i, k - i * n));
  }
  x3 = min(x3, x4);
  x2 = min(x2, x3);
  return ret = min(x1, x2);
}
int main() {
  memset(dp, -1, sizeof(dp));
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    cout << solve(n, m, k) << endl;
  }
  return 0;
}
