#include <bits/stdc++.h>
using namespace std;
int dp[31][31][51];
void calcule() {
  for (int n = 1; n <= 30; n++)
    for (int m = 1; m <= 30; m++) {
      for (int k = 0; k <= 50; k++) {
        if (k == 0)
          dp[n][m][0] = 0;
        else if (n * m == k)
          dp[n][m][k] = 0;
        else if (n * m < k)
          dp[n][m][k] = (long long)(1e9 + 7);
        else {
          dp[n][m][k] = (long long)(1e9 + 7);
          for (int n1 = 1; n1 < n; n1++)
            for (int k1 = 0; k1 <= k; k1++)
              dp[n][m][k] = min(dp[n][m][k],
                                m * m + dp[n1][m][k1] + dp[n - n1][m][k - k1]);
          for (int m1 = 1; m1 < m; m1++)
            for (int k1 = 0; k1 <= k; k1++)
              dp[n][m][k] = min(dp[n][m][k],
                                n * n + dp[n][m1][k1] + dp[n][m - m1][k - k1]);
        }
      }
    }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  calcule();
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    int answer = dp[n][m][k];
    cout << answer << '\n';
  }
  return 0;
}
