#include <bits/stdc++.h>
using namespace std;
const double PI = (double)3.141592653589793238462643383279502884L;
const long long MOD = 1000000007;
void ioFromFile(string inputFileName = "input.txt",
                string outputFileName = "output.txt") {
  ifstream* fin = new ifstream(inputFileName);
  ofstream* fout = new ofstream(outputFileName);
  cin.rdbuf(fin->rdbuf());
  cout.rdbuf(fout->rdbuf());
}
int read() {
  int x;
  scanf("%d", &x);
  return x;
}
void write(int x) { printf("%d ", x); }
int d[31][31][51];
int f(int h, int w, int k) {
  if (k > h * w) return -1;
  int& dd = d[h][w][k];
  if (dd != -1) return dd;
  if (k == 0) return dd = 0;
  if (k == w * h) return dd = 0;
  int res = -2;
  for (int y = 1; y < h; y++) {
    for (int i = 0; i <= k; i++) {
      int a = f(y, w, i);
      if (a < 0) continue;
      int b = f(h - y, w, k - i);
      if (b < 0) continue;
      int newres = w * w + a + b;
      if (res < 0 || newres < res) {
        res = newres;
      }
    }
  }
  for (int x = 1; x < w; x++) {
    for (int i = 0; i <= k; i++) {
      int a = f(h, x, i);
      if (a < 0) continue;
      int b = f(h, w - x, k - i);
      if (b < 0) continue;
      int newres = h * h + a + b;
      if (res < 0 || newres < res) {
        res = newres;
      }
    }
  }
  return dd = res;
}
int main() {
  memset(d, -1, sizeof(d));
  int n = read();
  while (n--) {
    int h = read();
    int w = read();
    int k = read();
    write(f(h, w, k));
  }
  return 0;
}
