#include <bits/stdc++.h>
using namespace std;
long long x, y, p;
long long dp[31][31][51];
long long foo(long long m, long long n, long long c) {
  if (dp[m][n][c] || !c || m * n == c) return dp[m][n][c];
  long long ans = INT_MAX;
  for (long long i = 1; i + i <= m; i++)
    for (long long j = 0; j <= c; j++)
      ans = min(ans, n * n + foo(m - i, n, j) + foo(i, n, c - j));
  for (long long i = 1; i + i <= n; i++)
    for (long long j = 0; j <= c; j++)
      ans = min(ans, m * m + foo(m, n - i, j) + foo(m, i, c - j));
  return dp[m][n][c] = ans;
}
int main() {
  long long n;
  cin >> n;
  while (n--) {
    cin >> x >> y >> p;
    cout << foo(x, y, p) << endl;
  }
  return 0;
}
