#include <bits/stdc++.h>
using namespace std;
long long dp[31][31][51];
void fill() {
  for (int i = 0; i < 31; i++)
    for (int j = 0; j < 31; j++)
      for (int k = 0; k < 51; k++) dp[i][j][k] = 10000000000000;
}
long long solve(int x, int y, int k) {
  if (x * y == k || k == 0) return dp[x][y][k] = 0, dp[y][x][k] = 0, 0;
  if (dp[x][y][k] != 10000000000000 || x * y < k) return dp[x][y][k];
  for (int i = 1; i < x; i++) {
    for (int j = 0; j <= k; j++) {
      dp[x][y][k] =
          min(dp[x][y][k], solve(i, y, j) + solve(x - i, y, k - j) + y * y);
    }
  }
  for (int i = 1; i < y; i++) {
    for (int j = 0; j <= k; j++) {
      dp[x][y][k] =
          min(dp[x][y][k], solve(x, i, j) + solve(x, y - i, k - j) + x * x);
    }
  }
  dp[x][y][k] = min(dp[y][x][k], dp[x][y][k]);
  dp[y][x][k] = dp[x][y][k];
  return dp[x][y][k];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  fill();
  for (int i = 30; i >= 1; i--)
    for (int j = 30; j >= 1; j--)
      for (int k = 50; k > 0; k--) solve(i, j, k);
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << dp[n][m][k] << '\n';
  }
  return 0;
}
