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