#include <bits/stdc++.h>
using namespace std;
int dp[40][40][60];
int N, M, K;
int dfs(int w, int l, int c) {
  int i, j, k;
  if (c == w * l) return dp[w][l][c] = 0;
  if (c == 0) return dp[w][l][c] = 0;
  if (w * l < c) return 0x3f3f3f3f;
  if (dp[w][l][c] != -1) return dp[w][l][c];
  dp[w][l][c] = 0x3f3f3f3f;
  for (i = 1; i < w; i++)
    for (j = 0; j <= c; j++) {
      if (i * l < j || (w - i) * l < (c - j)) continue;
      dp[w][l][c] =
          min(dp[w][l][c], dfs(i, l, j) + dfs(w - i, l, c - j) + l * l);
    }
  for (i = 1; i < l; i++)
    for (j = 0; j <= c; j++) {
      if (i * w < j || (l - i) * w < (c - j)) continue;
      dp[w][l][c] =
          min(dp[w][l][c], dfs(w, i, j) + dfs(w, l - i, c - j) + w * w);
    }
  return dp[w][l][c];
}
int main() {
  int i, j, k;
  int T, t;
  cin >> T;
  memset(dp, -1, sizeof(dp));
  for (t = 0; t < T; t++) {
    cin >> N >> M >> K;
    dfs(N, M, K);
    cout << dp[N][M][K] << "\n";
  }
  return 0;
}
