#include <bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int dp[100][100][100];
int solve(int n, int m, int k) {
  if (n * m == k or k == 0) {
    return 0;
  }
  if (dp[n][m][k] != -1) {
    return dp[n][m][k];
  }
  int ans = 1e9;
  for (int i = 1; n > i; i++) {
    if (i * m <= k) {
      ans = min(ans, solve(n - i, m, k - m * i) + m * m);
      continue;
    }
    ans = min(ans, solve(i, m, k) + m * m);
  }
  for (int i = 1; m > i; i++) {
    if (i * n <= k) {
      ans = min(ans, solve(n, m - i, k - n * i) + n * n);
      continue;
    }
    ans = min(ans, solve(n, i, k) + n * n);
  }
  return dp[n][m][k] = ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  memset(dp, -1, sizeof(dp));
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << solve(n, m, k) << "\n";
  }
}
