#include <bits/stdc++.h>
using namespace std;
long long dp[31][31][51];
void Cal() {
  for (int i = 0; i <= 30; i++)
    for (int j = 0; j <= 30; j++)
      for (int k = 0; k <= 50; k++) {
        dp[i][j][k] = (k == 0 || k == i * j) ? 0 : 10000000000000000;
        for (int kk = 0; kk <= k; kk++) {
          for (int ii = 1; ii < i; ii++)
            dp[i][j][k] =
                min(dp[i][j][k], dp[ii][j][kk] + dp[i - ii][j][k - kk] + j * j);
          for (int jj = 1; jj < j; jj++)
            dp[i][j][k] =
                min(dp[i][j][k], dp[i][jj][kk] + dp[i][j - jj][k - kk] + i * i);
        }
      }
}
int main() {
  int T;
  scanf("%d", &T);
  Cal();
  while (T--) {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    cout << dp[n][m][k] << endl;
  }
  return 0;
}
