#include <bits/stdc++.h>
using namespace std;
int t, n, m, k;
int dp[55][55][60];
int main() {
  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] = 99999999;
        if (k == 0 || i * j == 0 || i * j == k) dp[i][j][k] = 0;
        for (int c = 0; c <= k; c++) {
          for (int x = 1; x < i; x++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[x][j][c] + dp[i - x][j][k - c] + j * j);
          }
          for (int y = 1; y < j; y++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[i][y][c] + dp[i][j - y][k - c] + i * i);
          }
        }
      }
  cin >> t;
  for (int i = 1; i <= t; i++) {
    cin >> n >> m >> k;
    cout << dp[n][m][k] << endl;
  }
  return 0;
}
