#include <bits/stdc++.h>
using namespace std;
int a[32][32][52];
int count(int n, int m, int k) {
  if (a[n][m][k] != -1) return a[n][m][k];
  int c1 = n * n;
  int c2 = m * m;
  int cost = INT_MAX;
  for (int i = 1; i <= (m / 2); i++) {
    for (int l = 0; l <= k; l++) {
      if (n * i < l || (n * (m - i) < k - l)) {
        continue;
      }
      int tempCost = c1 + count(n, i, l) + count(n, m - i, k - l);
      cost = tempCost < cost ? tempCost : cost;
    }
  }
  for (int i = 1; i <= (n / 2); i++) {
    for (int l = 0; l <= k; l++) {
      if (m * i < l || ((n - i) * m < (k - l))) {
        continue;
      }
      int tempCost = c2 + count(i, m, l) + count(n - i, m, k - l);
      cost = tempCost < cost ? tempCost : cost;
    }
  }
  a[n][m][k] = cost;
  a[m][n][k] = cost;
  return cost;
}
int main() {
  for (int i = 0; i <= 31; i++) {
    for (int j = 0; j <= 31; j++) {
      for (int l = 0; l <= 51; l++) {
        if (l == 0) {
          a[i][j][l] = 0;
        } else if ((i * j) == l) {
          a[i][j][l] = 0;
        } else {
          a[i][j][l] = -1;
        }
      }
    }
  }
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int n, m, k;
    cin >> n;
    cin >> m;
    cin >> k;
    cout << count(n, m, k) << endl;
  }
  return 0;
}
