#include <bits/stdc++.h>
using namespace std;
int f[32][32][53];
int T;
int n, m, k;
int dp(int x, int y, int k) {
  if (~f[x][y][k]) return f[x][y][k];
  if (x * y == k) return f[x][y][k] = 0;
  if (k == 0) return f[x][y][k] = 0;
  int &ret = f[x][y][k];
  ret = 1 << 30;
  for (int i(1); i <= (x - 1); ++i) {
    for (int j(0); j <= (k); ++j) {
      if (i * y >= j && (x - i) * y >= k - j) {
        int c1 = dp(i, y, j), c2 = dp(x - i, y, k - j);
        ret = min(ret, y * y + c1 + c2);
      }
    }
  }
  for (int j(1); j <= (y - 1); ++j) {
    for (int i(0); i <= (k); ++i) {
      if (x * j >= i && x * (y - j) >= k - i) {
        int c1 = dp(x, j, i), c2 = dp(x, y - j, k - i);
        ret = min(ret, x * x + c1 + c2);
      }
    }
  }
  return ret;
}
int main() {
  memset(f, -1, sizeof f);
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &n, &m, &k);
    printf("%d\n", dp(n, m, k));
  }
  return 0;
}
