#include <bits/stdc++.h>
using namespace std;
long long dp[31][31][51];
long long t, n, m, k;
long long getDP(long long i, long long j, long long k) {
  if (dp[i][j][k] < 1e9) return dp[i][j][k];
  if (!k || k == i * j) {
    return dp[i][j][k] = 0;
  }
  for (long long l = 1; l < i; ++l) {
    for (long long m = 0; m < k / 2 + 1; ++m) {
      if (l * j < m || (i - l) * j < k - m) continue;
      dp[i][j][k] =
          min(dp[i][j][k], getDP(l, j, m) + getDP(i - l, j, k - m) + j * j);
    }
    for (long long m = 0; m < k / 2 + 1; ++m) {
      if ((i - l) * j < m || l * j < k - m) continue;
      dp[i][j][k] =
          min(dp[i][j][k], getDP(l, j, k - m) + getDP(i - l, j, m) + j * j);
    }
  }
  for (long long l = 1; l < j; ++l) {
    for (long long m = 0; m < k / 2 + 1; ++m) {
      if (l * i < m || (j - l) * i < k - m) continue;
      dp[i][j][k] =
          min(dp[i][j][k], getDP(i, l, m) + getDP(i, j - l, k - m) + i * i);
    }
    for (long long m = 0; m < k / 2 + 1; ++m) {
      if ((j - l) * i < m || l * i < k - m) continue;
      dp[i][j][k] =
          min(dp[i][j][k], getDP(i, l, k - m) + getDP(i, j - l, m) + i * i);
    }
  }
  return dp[i][j][k];
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  for (long long i = 1; i < 31; ++i) {
    for (long long j = 1; j < 31; ++j) {
      for (long long k = 1; k < min(i * j, 50LL) + 1; ++k) {
        dp[i][j][k] = 1e9;
      }
    }
  }
  for (long long i = 1; i < 31; ++i) {
    for (long long j = 1; j < 31; ++j) {
      for (long long k = 1; k < min(i * j, 50LL) + 1; ++k) {
        dp[i][j][k] = getDP(i, j, k);
      }
    }
  }
  cin >> t;
  for (long long i = 0; i < t; ++i) {
    cin >> n >> m >> k;
    cout << dp[n][m][k] << '\n';
  }
  return 0;
}
