#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000;
int f[35][35][55];
int gao(int x, int y, int z) {
  if (f[x][y][z] > 0) return f[x][y][z];
  if (z == 0) return f[x][y][z] = 0;
  if (x * y < z) return f[x][y][z] = inf;
  if (x * y == z) return f[x][y][z] = 0;
  int now = inf;
  for (int i = 1; i <= z; i++) {
    int cnt = inf;
    for (int j = 1; j < x; j++)
      cnt = min(cnt, gao(j, y, i) + gao(x - j, y, z - i) + y * y);
    for (int j = 1; j < y; j++)
      cnt = min(cnt, gao(x, j, i) + gao(x, y - j, z - i) + x * x);
    now = min(now, cnt);
  }
  return f[x][y][z] = now;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    printf("%d\n", gao(n, m, k));
  }
  return 0;
}
