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