#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-9;
int n, m, k;
long long dp[35][35][100];
long long dfs(int l, int r, int t) {
  if (l * r < t) return 999999999;
  if (l > r) swap(l, r);
  if (dp[l][r][t] != -1) return dp[l][r][t];
  if (t == 0) {
    dp[l][r][t] = 0;
    return 0;
  }
  if (l * r == t) return 0;
  long long ans1 = 9999999999999LL;
  for (int i = 1; i < l; i++)
    for (int j = 0; j <= t; j++)
      ans1 = min(ans1, dfs(i, r, j) + dfs(l - i, r, t - j) + r * r);
  for (int i = 1; i < r; i++)
    for (int j = 0; j <= t; j++)
      ans1 = min(ans1, dfs(l, i, j) + dfs(l, r - i, t - j) + l * l);
  if (dp[l][r][t] != -1)
    dp[l][r][t] = min(dp[l][r][t], ans1);
  else
    dp[l][r][t] = ans1;
  return dp[l][r][t];
}
int main() {
  int t;
  scanf("%d", &t);
  memset(dp, -1, sizeof(dp));
  while (t--) {
    scanf("%d%d%d", &n, &m, &k);
    printf("%I64d\n", dfs(n, m, k));
  }
}
