#include <bits/stdc++.h>
using namespace std;
int t, n, m, k;
int dp[32][32][52];
int solve(int n, int m, int rem) {
  if (!rem) return 0;
  if (rem > n * m) return 1e9;
  if (dp[n][m][rem] != -1) return dp[n][m][rem];
  if (n * m == rem) return dp[n][m][rem] = 0;
  int &ret = dp[n][m][rem];
  ret = 1e9;
  for (int p = (0); p <= (int)(rem); ++p) {
    for (int i = (1); i <= (int)(n - 1); ++i)
      ret = min(ret, m * m + solve(i, m, p) + solve(n - i, m, rem - p));
    for (int j = (1); j <= (int)(m - 1); ++j)
      ret = min(ret, n * n + solve(n, j, p) + solve(n, m - j, rem - p));
  }
  return ret;
}
int main() {
  memset(dp, -1, sizeof dp);
  for (int i = (0); i <= (int)(30); ++i)
    for (int j = (0); j <= (int)(30); ++j)
      for (int k = (0); k <= (int)(50); ++k) solve(i, j, k);
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &n, &m, &k);
    printf("%d\n", dp[n][m][k]);
  }
}
