#include <bits/stdc++.h>
using namespace std;
const int MAXI = 1000000000;
int d[31][31][51];
int t;
int calc(int n, int m, int k) {
  if (d[n][m][k] < MAXI) return d[n][m][k];
  if (n * m == k || k == 0) return 0;
  if (n * m < k) return MAXI;
  for (int i = 1; i <= (n) / 2; ++i) {
    for (int j = 0; j < k + 1; ++j) {
      int t = calc(i, m, j);
      int b = calc(n - i, m, k - j);
      d[n][m][k] = min(d[n][m][k], t + b + m * m);
    }
  }
  for (int i = 1; i <= (m) / 2; ++i) {
    for (int j = 0; j < k + 1; ++j) {
      int l = calc(n, i, j);
      int r = calc(n, m - i, k - j);
      d[n][m][k] = min(d[n][m][k], l + r + n * n);
    }
  }
  return d[n][m][k];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 0; i < 31; i++)
    for (int j = 0; j < 31; j++)
      for (int l = 0; l < 51; l++) d[i][j][l] = MAXI;
  cin >> t;
  vector<int> n(t, 0);
  vector<int> m(t, 0);
  vector<int> k(t, 0);
  for (int i = 0; i < t; ++i) {
    cin >> n[i] >> m[i] >> k[i];
  }
  for (int i = 0; i < t; ++i) {
    cout << calc(n[i], m[i], k[i]) << endl;
  }
  return 0;
}
