#include <bits/stdc++.h>
using namespace std;
int n, m, k;
bool vis[35][35][55];
int f[35][35][55];
void readinp() { cin >> n >> m >> k; }
int dp(int i, int j, int d) {
  if (d < 0 || i * j < d || !i || !j) return 1e9;
  if (i * j == d || !d) return 0;
  if (i > j) swap(i, j);
  if (vis[i][j][d]) return f[i][j][d];
  vis[i][j][d] = true;
  int ret = 1e9;
  for (int l = int(0); l <= int(j / 2 + 1); l++)
    for (int c = int(0); c <= int(d); c++) {
      ret = min(ret, dp(i, j - l, c) + dp(i, l, d - c) + i * i);
    }
  if (i != j)
    for (int l = int(0); l <= int(i / 2); l++)
      for (int c = int(0); c <= int(d); c++) {
        ret = min(ret, dp(i - l, j, c) + dp(l, j, d - c) + j * j);
      }
  f[i][j][d] = ret;
  return ret;
}
void solve() { cout << dp(n, m, k), cout << '\n'; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  if (fopen("598E"
            ".inp",
            "r")) {
    freopen(
        "598E"
        ".inp",
        "r", stdin);
    freopen(
        "598E"
        ".out",
        "w", stdout);
  }
  int t = 1;
  cin >> t;
  while (t--) {
    readinp();
    solve();
  }
}
