#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-10;
const double PI = acos(-1.0);
int dp[51][51][51];
int dfs(int n, int m, int k) {
  if (dp[n][m][k] >= 0) return dp[n][m][k];
  if (k == 0 || n * m == k) return dp[n][m][k] = 0;
  dp[n][m][k] = 1e9;
  for (int j = 0; j <= k; ++j) {
    for (int i = 1; i < n; ++i)
      dp[n][m][k] =
          min(dp[n][m][k], dfs(n - i, m, k - j) + dfs(i, m, j) + m * m);
    for (int i = 1; i < m; ++i)
      dp[n][m][k] =
          min(dp[n][m][k], dfs(n, m - i, k - j) + dfs(n, i, j) + n * n);
  }
  return dp[n][m][k];
}
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  fill((int*)dp, (int*)dp + 51 * 51 * 51, -1);
  int T;
  cin >> T;
  while (T--) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << dfs(n, m, k) << endl;
  }
  return 0;
}
