#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7, G = 3;
const int base = 30000;
int t;
int n, m, k;
int dp[35][35][55];
int dfs(int n, int m, int k) {
  if (k == 0 || n * m == k) return 0;
  if (dp[n][m][k] != -1) return dp[n][m][k];
  int ret = INF;
  for (int i = 1; i < n; ++i)
    for (int j = 0; j <= k; ++j)
      ret = min(ret, dfs(i, m, j) + dfs(n - i, m, k - j) + m * m);
  for (int i = 1; i < m; ++i)
    for (int j = 0; j <= k; ++j)
      ret = min(ret, dfs(n, i, j) + dfs(n, m - i, k - j) + n * n);
  if (dp[n][m][k] == -1) dp[n][m][k] = ret;
  return ret;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> t;
  memset(dp, -1, sizeof(dp));
  while (t--) {
    cin >> n >> m >> k;
    cout << dfs(n, m, k) << '\n';
  }
  return 0;
}
