#include <bits/stdc++.h>
using namespace std;
long long n, m, k, dp[int(2 + 30)][int(2 + 30)][55];
long long Try(int N, int M, int K) {
  if (K == 0 || K == M * N) return 0;
  if (K < 0 || K > M * N) return 1e15;
  if (N > M) swap(N, M);
  long long &ret = dp[N][M][K];
  if (ret != -1) return ret;
  ret = 1e15;
  for (int i = 1; i <= M >> 1; i++)
    for (int j = 0; j <= K; j++)
      ret = min(ret, N * N + Try(N, i, j) + Try(N, M - i, K - j));
  for (int i = 1; i <= N >> 1; i++)
    for (int j = 0; j <= K; j++)
      ret = min(ret, M * M + Try(M, i, j) + Try(M, N - i, K - j));
  return ret;
}
int main() {
  long long T;
  cin >> T;
  memset(dp, -1, sizeof(dp));
  while (T--) {
    cin >> n >> m >> k;
    cout << Try(n, m, k) << endl;
  }
  return 0;
}
