#include <bits/stdc++.h>
using namespace std;
const int INF = 1061109567;
const long long LINF = 4557430888798830399ll;
const int MOD = 998244353;
long long dp[31][31][51];
void test_case() {
  memset(dp, LINF, sizeof(dp));
  for (int a = 0; a <= 30; ++a) {
    for (int b = 0; b <= 30; ++b) {
      dp[a][b][0] = 0;
      if (a * b <= 50) dp[a][b][a * b] = 0;
    }
  }
  for (int a = 1; a <= 30; ++a) {
    for (int b = 1; b <= a; ++b) {
      int ck = min(a * b - 1, 50);
      for (int k = 0; k <= ck; ++k) {
        long long tmp = dp[a][b][k];
        for (int a1 = 1; a1 < a; ++a1) {
          int cs = min(k, a1 * b);
          for (int s = 0, t = b * b; s <= cs && tmp > t; ++s) {
            tmp = min(tmp, dp[a1][b][s] + dp[a - a1][b][k - s] + t);
            tmp = min(tmp, dp[a1][b][k - s] + dp[a - a1][b][s] + t);
          }
        }
        for (int b1 = 1; b1 < b; ++b1) {
          int cs = min(k, b1 * a);
          for (int s = 0, t = a * a; s <= cs && tmp > t; ++s) {
            tmp = min(tmp, dp[a][b1][s] + dp[a][b - b1][k - s] + t);
            tmp = min(tmp, dp[a][b1][k - s] + dp[a][b - b1][s] + t);
          }
        }
        dp[a][b][k] = min(dp[a][b][k], tmp);
        dp[b][a][k] = min(dp[b][a][k], tmp);
      }
    }
  }
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    printf("%lld\n", dp[n][m][k]);
  }
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    test_case();
  }
  return 0;
}
