#include <bits/stdc++.h>
using namespace std;
const int maxn = 33;
const int maxk = 55;
long long int dp[maxn][maxn][maxk];
long long int f(long long int n, long long int m, long long int k) {
  if (n * m == k || k == 0) return 0;
  long long int ans = INT_MAX;
  if (dp[n][m][k]) return dp[n][m][k];
  for (int(i) = (1); (i) < (n); (i)++)
    for (int(j) = (0); (j) < (k + 1); (j)++)
      ans = min(ans, (m * m) + f(i, m, k - j) + f(n - i, m, j));
  for (int(i) = (1); (i) < (m); (i)++)
    for (int(j) = (0); (j) < (k + 1); (j)++)
      ans = min(ans, n * n + f(n, i, k - j) + f(n, m - i, j));
  return dp[n][m][k] = ans;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long int n, m, k;
    cin >> n >> m >> k;
    cout << f(n, m, k) << '\n';
  }
}
