#include <bits/stdc++.h>
using namespace std;
int dp[31][31][51];
int solve(int i, int j, int k) {
  if (i <= 0 || j <= 0) return 1e9;
  if (i * j == k || k <= 0) return 0;
  if (dp[i][j][k] != -1) return dp[i][j][k];
  int op = 1e9;
  for (int x = 1; x <= i; ++x)
    for (int y = 1; y <= k; ++y)
      op = min(op, j * j + solve(i - x, j, y) + solve(x, j, k - y));
  for (int x = 1; x <= j; ++x)
    for (int y = 1; y <= k; ++y)
      op = min(op, i * i + solve(i, j - x, y) + solve(i, x, k - y));
  return dp[i][j][k] = op;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  memset(dp, -1, sizeof(dp));
  int t, n, m, k;
  cin >> t;
  while (t--) {
    cin >> n >> m >> k;
    cout << solve(n, m, k) << '\n';
  }
}
