#include <bits/stdc++.h>
using namespace std;
int dp[32][32][52];
int main() {
  memset(dp, 0x0f, sizeof(dp));
  for (int i = 1; i <= 30; i++)
    for (int j = 1; j <= 30; j++) {
      dp[i][j][0] = 0;
      if (i * j <= 50) dp[i][j][i * j] = 0;
    }
  for (int i = 1; i <= 30; i++)
    for (int j = 1; j <= 30; j++)
      for (int k = min(50, i * j); k; k--) {
        if (i > j) {
          dp[i][j][k] = dp[j][i][k];
          continue;
        }
        int &ret = dp[i][j][k];
        for (int t = 1; t < i; t++) {
          for (int t1 = 0; t1 <= k; t1++) {
            ret = min(ret, dp[t][j][t1] + dp[i - t][j][k - t1] + j * j);
          }
        }
        for (int t = 1; t < j; t++) {
          for (int t1 = 0; t1 <= k; t1++) {
            ret = min(ret, dp[i][t][t1] + dp[i][j - t][k - t1] + i * i);
          }
        }
      }
  int t, x, y, k;
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    scanf("%d%d%d", &x, &y, &k);
    printf("%d\n", dp[x][y][k]);
  }
  return 0;
}
