#include <bits/stdc++.h>
using namespace std;
int dp[31][31][51];
int func(int a, int b, int c) {
  if (dp[a][b][c] || a * b == c || c == 0) return dp[a][b][c];
  int &ret = dp[a][b][c];
  ret = 1e9;
  for (int i = 1; i <= a - i; i++) {
    for (int k1 = 0; k1 <= c; k1++)
      ret = min(ret, b * b + func(i, b, c - k1) + func(a - i, b, k1));
  }
  for (int i = 1; i <= b - i; i++) {
    for (int k1 = 0; k1 <= c; k1++)
      ret = min(ret, a * a + func(a, i, k1) + func(a, b - i, c - k1));
  }
  return ret;
}
int main() {
  int n, m, k, tc;
  scanf("%d", &tc);
  while (tc--) {
    scanf("%d %d %d", &n, &m, &k);
    int ans = func(n, m, k);
    printf("%d\n", ans);
  }
}
