#include <bits/stdc++.h>
using namespace std;
int t;
int n, m, k, dp[35][35][55];
int calc(int row, int col, int need) {
  if (need == 0 || (row * col == need)) return 0;
  if (dp[row][col][need] != -1) return dp[row][col][need];
  int ret = 1e9;
  for (int i = 1; i <= (col - 1); i++) {
    int have = i * row, chose = 1e9;
    if (have <= need) chose = (row * row) + calc(row, col - i, need - have);
    chose = min(chose, (row * row) + calc(row, col - i, need));
    ret = min(ret, chose);
  }
  for (int i = 1; i <= (row - 1); i++) {
    int have = col * i, chose = 1e9;
    if (have <= need) chose = (col * col) + calc(row - i, col, need - have);
    chose = min(chose, (col * col) + calc(row - i, col, need));
    ret = min(ret, chose);
  }
  return dp[row][col][need] = ret;
}
int main() {
  cin >> t;
  memset(dp, -1, sizeof(dp));
  while (t--) {
    cin >> n >> m >> k;
    cout << calc(n, m, k) << endl;
  }
  return 0;
}
