#include <bits/stdc++.h>
using namespace std;
long long dp[31][31][51];
long long solve(long long n, long long m, long long k) {
  if (n * m == k || k == 0) return 0;
  if (n * m < k) return 1e15;
  if (dp[n][m][k] != -1) return dp[n][m][k];
  long long ans = 1e15;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j <= k; j++) {
      ans = min(ans, solve(i, m, j) + solve(n - i, m, k - j) + m * m);
    }
  }
  for (int i = 1; i < m; i++) {
    for (int j = 0; j <= k; j++) {
      ans = min(ans, solve(n, i, j) + solve(n, m - i, k - j) + n * n);
    }
  }
  return dp[n][m][k] = ans;
}
int main() {
  long long tc;
  cin >> tc;
  memset(dp, -1, sizeof dp);
  while (tc--) {
    long long n, m, k;
    cin >> n >> m >> k;
    cout << solve(n, m, k) << endl;
  }
}
