#include <bits/stdc++.h>
int dp[30 + 1][30 + 1][50 + 1];
int Min(int a, int b) { return a < b ? a : b; }
void SubDP(int i, int j, int s) {
  int halfi = i >> 1;
  int halfj = j >> 1;
  int totSize = 0;
  int tmp;
  for (int subi = 1, tots = j; subi <= halfi; ++subi, tots += j) {
    for (int subs = 0; subs <= tots && subs <= s; ++subs) {
      tmp = dp[subi][j][subs] + dp[i - subi][j][s - subs] + j * j;
      dp[i][j][s] = Min(dp[i][j][s], tmp);
    }
  }
  for (int subj = 1, tots = i; subj <= halfj; ++subj, tots += i) {
    for (int subs = 0; subs <= tots && subs <= s; ++subs) {
      tmp = dp[i][subj][subs] + dp[i][j - subj][s - subs] + i * i;
      dp[i][j][s] = Min(dp[i][j][s], tmp);
    }
  }
}
void DP() {
  for (int i = 1; i <= 30; ++i) {
    for (int j = 1; j <= 30; ++j) {
      dp[i][j][0] = 0;
      for (int k = 1; k <= 50; ++k) {
        dp[i][j][k] = 0xfffffff;
      }
    }
  }
  dp[1][1][1] = 0;
  dp[1][1][0] = 0;
  for (int i = 2; i <= 30; ++i) {
    dp[i][1][0] = 0;
    dp[1][i][0] = 0;
    dp[i][1][i] = 0;
    dp[1][i][i] = 0;
    for (int s = 1; s < i; ++s) {
      dp[i][1][s] = 1;
      dp[1][i][s] = 1;
    }
  }
  for (int i = 2; i <= 30; ++i) {
    for (int j = 2; j <= i; ++j) {
      int totSize = i * j;
      if (totSize <= 50) {
        dp[i][j][i * j] = 0;
        dp[j][i][i * j] = 0;
      }
      dp[i][j][0] = 0;
      dp[j][i][0] = 0;
      for (int s = 1; s < totSize && s <= 50; ++s) {
        SubDP(i, j, s);
        dp[j][i][s] = dp[i][j][s];
      }
    }
  }
}
void PrintDp() {
  for (int i = 1; i <= 30; ++i) {
    for (int j = 1; j <= 30; ++j) {
      for (int k = 1; k <= 50 && k <= i * j; ++k) {
        printf("%d %d %d %d\n", i, j, k, dp[i][j][k]);
      }
    }
  }
}
int main() {
  DP();
  int ncase, n, m, k;
  scanf("%d%*c", &ncase);
  while (ncase--) {
    scanf("%d%*c%d%*c%d%*c", &n, &m, &k);
    printf("%d\n", dp[n][m][k]);
  }
}
