#include <bits/stdc++.h>
int dp[31][31][51];
int calc(int n, int m, int k) {
  if (dp[n][m][k] || !k || k == n * m) return dp[n][m][k];
  int rlt = 1000000000;
  for (int i = 1; i + i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      int tmp = m * m + calc(i, m, j) + calc(n - i, m, k - j);
      if (rlt > tmp) rlt = tmp;
    }
  }
  for (int i = 1; i + i <= m; i++) {
    for (int j = 0; j <= k; j++) {
      int tmp = n * n + calc(n, i, j) + calc(n, m - i, k - j);
      if (rlt > tmp) rlt = tmp;
    }
  }
  return dp[n][m][k] = rlt;
}
int main() {
  int T, n, m, k;
  for (scanf("%d", &T); T--;) {
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", calc(n, m, k));
  }
}
