#include <bits/stdc++.h>
using namespace std;
int TC, n, m, k, memo[31][31][51];
int sol(int r, int c, int need) {
  if (memo[r][c][need] != -1) return memo[r][c][need];
  if (r * c == need || need == 0) return memo[r][c][need] = 0;
  int mini = 123456789;
  for (int i = 1; i < r; i++) {
    for (int j = 0; j <= need; j++)
      mini = min(mini, c * c + sol(r - i, c, need - j) + sol(i, c, j));
  }
  for (int i = 1; i < c; i++) {
    for (int j = 0; j <= need; j++)
      mini = min(mini, r * r + sol(r, c - i, need - j) + sol(r, i, j));
  }
  return memo[r][c][need] = mini;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  memset(memo, -1, sizeof memo);
  cin >> TC;
  while (TC--) {
    cin >> n >> m >> k;
    cout << sol(n, m, k) << "\n";
  }
  return 0;
}
