#include <bits/stdc++.h>
using namespace std;
int xxx;
int dp[50][50][60];
const int INF = 999999999;
int main() {
  for (register int i = 0; i <= 30; i++) {
    for (register int j = 0; j <= 30; j++) {
      for (register int k = 0; k <= 50; k++) {
        dp[i][j][k] = INF;
        if (k == 0 || k == i * j || i * j == 0) dp[i][j][k] = 0;
        for (register int a = 0; a <= k; a++) {
          for (register int b = 1; b < i; b++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[b][j][a] + dp[i - b][j][k - a] + j * j);
          }
          for (register int c = 1; c < j; c++) {
            dp[i][j][k] =
                min(dp[i][j][k], dp[i][c][a] + dp[i][j - c][k - a] + i * i);
          }
        }
      }
    }
  }
  cin >> xxx;
  while (xxx) {
    register int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    printf("%d\n", dp[n][m][k]);
    xxx--;
  }
}
