#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const int MOD = 1e9 + 7;
long long power(long long a, long long b) {
  if (b == 0)
    return 1;
  else {
    long long x = power(a, b / 2);
    x = (x * x) % MOD;
    if (b & 1)
      return (x * a) % MOD;
    else
      return x;
  }
}
long long &Mod(long long &a) {
  if (a >= MOD) {
    return Mod(a -= MOD);
  } else if (a < 0) {
    return Mod(a += MOD);
  } else {
    return a;
  }
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
const int N = 35;
const int K = 55;
long long dp[N][N][K];
long long rec(int x, int y, int p) {
  if (x * y == p or p == 0) {
    dp[x][y][p] = 0;
    return 0;
  }
  if (dp[x][y][p] != -1) {
    return dp[x][y][p];
  }
  long long res = 1e18;
  for (int i = 1; i < y; i++) {
    for (int ch = 0; ch <= min(x * i, p); ch++) {
      if ((x * (y - i)) >= (p - ch)) {
        res =
            min(res, (long long)x * x + rec(x, i, ch) + rec(x, y - i, p - ch));
      }
    }
  }
  for (int i = 1; i < x; i++) {
    for (int ch = 0; ch <= min(i * y, p); ch++) {
      if ((x - i) * y >= (p - ch)) {
        res =
            min(res, (long long)y * y + rec(i, y, ch) + rec(x - i, y, p - ch));
      }
    }
  }
  dp[x][y][p] = res;
  return dp[x][y][p];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = 0; k < K; k++) {
        dp[i][j][k] = -1;
      }
    }
  }
  rec(N - 2, N - 2, K - 2);
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << dp[n][m][k] << '\n';
  }
}
