#include <bits/stdc++.h>
const int N = 31;
const int K = 51;
const int INF = 1000000;
int dp[N][N][K];
bool flag[N][N][K];
int DP(int n, int m, int k) {
  if (n > m) std::swap(n, m);
  if (flag[n][m][k]) return dp[n][m][k];
  flag[n][m][k] = true;
  dp[n][m][k] = INF;
  if (k == n * m || k == 0) return (dp[n][m][k] = 0);
  if (k > n * m) return INF;
  for (int i = 1; i * 2 <= n; i++)
    for (int j = 0; j <= k; j++)
      dp[n][m][k] =
          std::min(dp[n][m][k], DP(i, m, j) + DP(n - i, m, k - j) + m * m);
  for (int i = 1; i * 2 <= m; i++)
    for (int j = 0; j <= k; j++)
      dp[n][m][k] =
          std::min(dp[n][m][k], DP(n, i, j) + DP(n, m - i, k - j) + n * n);
  return dp[n][m][k];
}
int main() {
  int t;
  int n, m, k;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", DP(n, m, k));
  }
  return 0;
}
