#include <bits/stdc++.h>
using namespace std;
long long memo[51][31][31];
class Solution {
 public:
  pair<pair<pair<int, int>, pair<int, int>>, int> cut(int n, int m, int h = 0,
                                                      int v = 0) {
    if (h != 0) {
      pair<int, int> firstPart = make_pair(min(h, m), max(h, m));
      pair<int, int> secondPart = make_pair(min(n - h, m), max(n - h, m));
      int cost = m * m;
      return make_pair(make_pair(firstPart, secondPart), cost);
    } else {
      pair<int, int> firstPart = make_pair(min(n, v), max(n, v));
      pair<int, int> secondPart = make_pair(min(n, m - v), max(n, m - v));
      int cost = n * n;
      return make_pair(make_pair(firstPart, secondPart), cost);
    }
  }
  pair<pair<pair<int, int>, pair<int, int>>, int> cut(pair<int, int> bar,
                                                      int h = 0, int v = 0) {
    return cut(bar.first, bar.second, h, v);
  }
  void solve(std::istream& in, std::ostream& out) {
    for (int i = 0; i < 51; i++) {
      for (int j = 0; j < 31; j++) {
        for (int k = 0; k < 31; k++) {
          memo[i][j][k] = 30 * 30 * 30 * 30;
        }
      }
    }
    int maxN = 31;
    int maxK = 51;
    for (int n = 0; n < maxN; n++) {
      for (int m = n; m < maxN; m++) {
        for (int k = 0; k < maxK; k++) {
          if (k <= n * m) {
            pair<int, int> bar = make_pair(n, m);
            if (k == 0 || n == 0 || m == 0 || (k == n * m))
              memo[k][n][m] = 0;
            else {
              long long ans = 30 * 30 * 30 * 30;
              for (int h = 1; h < n; h++) {
                auto afterCut = cut(bar, h, 0);
                auto leftPart = afterCut.first.first;
                int a = leftPart.first;
                int b = leftPart.second;
                auto rightPart = afterCut.first.second;
                int f = rightPart.first;
                int g = rightPart.second;
                int cost = afterCut.second;
                for (int l = 0; l <= k; l++) {
                  int r = k - l;
                  if (l <= a * b && r <= f * g) {
                    long long newCost = cost + memo[l][a][b] + memo[r][f][g];
                    ans = min(ans, newCost);
                  }
                }
              }
              for (int v = 1; v < m; v++) {
                auto afterCut = cut(bar, 0, v);
                auto leftPart = afterCut.first.first;
                int a = leftPart.first;
                int b = leftPart.second;
                auto rightPart = afterCut.first.second;
                int f = rightPart.first;
                int g = rightPart.second;
                int cost = afterCut.second;
                for (int l = 0; l <= k; l++) {
                  int r = k - l;
                  if (l <= a * b && r <= f * g) {
                    long long newCost = cost + memo[l][a][b] + memo[r][f][g];
                    ans = min(ans, newCost);
                  }
                }
              }
              memo[k][n][m] = ans;
            }
          }
        }
      }
    }
    int t;
    in >> t;
    while (t--) {
      int n, m, k;
      in >> n >> m >> k;
      int a = min(n, m);
      int b = max(n, m);
      out << memo[k][a][b] << endl;
    }
  }
};
void solve(std::istream& in, std::ostream& out) {
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  istream& in = cin;
  ostream& out = cout;
  solve(in, out);
  return 0;
}
