#include <bits/stdc++.h>
using namespace std;
int dp[35][35][55];
int main() {
  ios_base::sync_with_stdio(false);
  cout.setf(ios::fixed);
  cout.setf(ios::showpoint);
  cout.precision(4);
  for (int i = 0; i < 32; i++) {
    for (int j = 0; j < 32; j++) {
      for (int k = 0; k < 52; k++) {
        dp[i][j][k] = int(1e9);
        if (k == 0 || k == i * j) dp[i][j][k] = 0;
        for (int v = 0; v <= k; v++) {
          for (int u = 1; u < i; u++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[u][j][v] + dp[i - u][j][k - v] + j * j);
          }
          for (int u = 1; u < j; u++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[i][u][v] + dp[i][j - u][k - v] + i * i);
          }
        }
      }
    }
  }
  int n;
  cin >> n;
  while (n--) {
    int a, b, k;
    cin >> a >> b >> k;
    cout << dp[a][b][k] << endl;
  }
  return 0;
}
