#include <bits/stdc++.h>
using namespace std;
int dp[31][31][51];
void init() {
  for (int i = 1; i < 31; i++) {
    for (int j = 1; j < 31; j++) {
      for (int k = (i * j) + 1; k < 51; k++) {
        dp[i][j][k] = 1000000009;
      }
    }
  }
  for (int i = 1; i < 31; i++) {
    for (int j = 1; j < 31; j++) {
      for (int k = 1; k < min(51, i * j); k++) {
        dp[i][j][k] = 1000000009;
        for (int x = 1; x < i; x++) {
          for (int l = 0; l < k; l++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[i - x][j][l] + dp[x][j][k - l] + j * j);
          }
        }
        for (int y = 1; y < j; y++) {
          for (int l = 0; l < k; l++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[i][j - y][l] + dp[i][y][k - l] + i * i);
          }
        }
      }
    }
  }
}
void solve() {
  int n, m, k;
  scanf("%d", &n);
  scanf("%d", &m);
  scanf("%d", &k);
  printf("%d\n", dp[n][m][k]);
}
int main() {
  init();
  int t = 1;
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    solve();
  }
}
