#include <bits/stdc++.h>
using namespace std;
void task();
int main() {
  ios_base::sync_with_stdio(0);
  task();
  return 0;
}
const int N = (int)1e5 + 10;
const long long int INF = (long long int)2e18 + 100;
const int MODULO = (int)1e9 + 7;
int dp[40][40][60];
bool calced[40][40][60];
int calc(int i, int j, int cnt) {
  if (calced[i][j][cnt]) return dp[i][j][cnt];
  if (cnt == 0) {
    calced[i][j][cnt] = 1;
    return dp[i][j][cnt] = 0;
  }
  if (cnt == i * j) {
    calced[i][j][cnt] = 1;
    return dp[i][j][cnt] = 0;
  }
  int mn = (int)1e9;
  (void(1));
  ;
  for (int ii = 1; ii < i; ++ii) {
    (void(1));
    ;
    for (int tc = 0; tc <= cnt; ++tc) {
      (void(1));
      ;
      mn = min(mn, calc(ii, j, tc) + calc(i - ii, j, cnt - tc) + j * j);
    }
  }
  for (int jj = 1; jj < j; ++jj) {
    for (int tc = 0; tc <= cnt; ++tc) {
      mn = min(mn, calc(i, jj, tc) + calc(i, j - jj, cnt - tc) + i * i);
    }
  }
  calced[i][j][cnt] = 1;
  (void(1));
  ;
  return dp[i][j][cnt] = mn;
}
int t;
void task() {
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << calc(n, m, k) << "\n";
  }
}
