#include <bits/stdc++.h>
using namespace std;
long long dp[31][31][55];
int main() {
  dp[1][1][1] = 0;
  for (int n = 1; n <= 30; n++)
    for (int m = 1; m <= 30; m++) {
      for (int k = 1; k <= min(n * m, 50); k++) {
        dp[n][m][k] = 1e18;
        if (k == n * m) {
          dp[n][m][k] = 0;
        } else {
          for (int i = 1; i <= n / 2; i++) {
            for (int p = 0; p <= k; p++)
              if (p <= m * i && (k - p) <= m * (n - i))
                dp[n][m][k] =
                    min(dp[n][m][k], dp[i][m][p] + dp[n - i][m][k - p] + m * m);
          }
          for (int i = 1; i <= m / 2; i++) {
            for (int p = 0; p <= k; p++)
              if (p <= n * i && (k - p) <= n * (m - i))
                dp[n][m][k] =
                    min(dp[n][m][k], dp[n][i][p] + dp[n][m - i][k - p] + n * n);
          }
        }
      }
    }
  int t;
  cin >> t;
  int n, m, k;
  for (int i = 0; i < t; i++) {
    scanf("%d %d %d", &n, &m, &k);
    printf("%I64d\n", dp[n][m][k]);
  }
  return 0;
}
