#include <bits/stdc++.h>
using namespace std;
int dp[31][31][51] = {0};
int main() {
  for (int i = 1; i <= 30; i++)
    for (int j = 1; j <= 30; j++)
      for (int k = 0; k <= 50; k++) {
        if (k == 0) {
          dp[i][j][k] = 0;
          continue;
        }
        if (i * j == k) {
          dp[i][j][k] = 0;
          continue;
        }
        int ans = INT_MAX;
        if (i * j < k)
          dp[i][j][k] = INT_MAX;
        else {
          for (int q = 1; q < j; q++) {
            for (int w = 1; w <= k; w++) {
              if (dp[i][q][w] == INT_MAX || dp[i][j - q][k - w] == INT_MAX)
                continue;
              ans = min(ans, dp[i][q][w] + dp[i][j - q][k - w] + i * i);
            }
          }
          for (int q = 1; q < i; q++) {
            for (int w = 1; w <= k; w++) {
              if (dp[q][j][w] == INT_MAX || dp[i - q][j][k - w] == INT_MAX)
                continue;
              ans = min(ans, dp[q][j][w] + dp[i - q][j][k - w] + j * j);
            }
          }
          dp[i][j][k] = ans;
          if (i == 1 && j == 1 && k == 1) dp[i][j][k] = 0;
        }
      }
  int t, a, b, c;
  cin >> t;
  for (int i = 0; i < t; i++) {
    scanf("%d%d%d", &a, &b, &c);
    printf("%d\n", dp[a][b][c]);
  }
}
