#include <bits/stdc++.h>
using namespace std;
const int maxint = -1u >> 1;
int dp[32][32][64];
int n, m, K, T;
void solve() {
  for (int i = 1; i <= 30; i++) {
    for (int j = 1; j <= 30; j++) {
      for (int k = 0; k <= 50; k++) {
        dp[i][j][k] = maxint;
        if (i * j == k || k == 0) {
          dp[i][j][k] = 0;
          continue;
        }
        if (i * j < k) continue;
        for (int z = 1; z < i; z++) {
          if (k - z * j >= 0)
            dp[i][j][k] = min(dp[i][j][k], dp[i - z][j][k - z * j] + j * j);
          if ((i - z) * j >= k)
            dp[i][j][k] = min(dp[i][j][k], dp[i - z][j][k] + j * j);
        }
        for (int z = 1; z < j; z++) {
          if (k - z * i >= 0)
            dp[i][j][k] = min(dp[i][j][k], dp[i][j - z][k - z * i] + i * i);
          if ((j - z) * i >= k)
            dp[i][j][k] = min(dp[i][j][k], dp[i][j - z][k] + i * i);
        }
      }
    }
  }
}
int main() {
  solve();
  cin >> T;
  while (T--) {
    cin >> n >> m >> K;
    cout << dp[n][m][K] << endl;
  }
  return 0;
}
