#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 33;
const int MAX_K = 55;
const int inf = 1000000007;
int dp[MAX_N][MAX_N][MAX_K];
int numTest, n, m, k;
void DynamicProgramming() {
  for (int i = 1; i < MAX_N; i++) {
    for (int j = 1; j < MAX_N; j++) {
      for (int x = 0; x < MAX_K; x++) {
        if (x == i * j || x == 0) {
          continue;
        }
        dp[i][j][x] = inf;
        for (int j1 = 1; j1 < j; j1++) {
          for (int x1 = 0; x1 <= x; x1++) {
            dp[i][j][x] =
                min(dp[i][j][x], dp[i][j1][x1] + dp[i][j - j1][x - x1] + i * i);
          }
        }
        for (int i1 = 1; i1 < i; i1++) {
          for (int x1 = 0; x1 <= x; x1++) {
            dp[i][j][x] =
                min(dp[i][j][x], dp[i1][j][x1] + dp[i - i1][j][x - x1] + j * j);
          }
        }
      }
    }
  }
}
int main() {
  DynamicProgramming();
  cin >> numTest;
  for (int testCase = 1; testCase <= numTest; testCase++) {
    cin >> n >> m >> k;
    cout << dp[n][m][k] << endl;
  }
  return 0;
}
