#include <bits/stdc++.h>
using namespace std;
const int MAXN = 31;
int dp[MAXN][MAXN][MAXN * MAXN];
int F(int n, int m, int k) {
  if (n > m) swap(n, m);
  if (k < 0) return (1 << 30);
  if (dp[n][m][k] != -1) return dp[n][m][k];
  if (n * m == k || k == 0) return dp[n][m][k] = 0;
  int p = 1 << 30, q = 1 << 30;
  for (int i = 1; i < n; i++)
    p = min(p, m * m + min(F(i, m, k - m * (n - i)), F(i, m, k)));
  for (int i = 1; i < m; i++)
    q = min(q, n * n + min(F(n, i, k - n * (m - i)), F(n, i, k)));
  return dp[n][m][k] = min(p, q);
}
int main() {
  int n, m, k, q;
  memset(dp, -1, sizeof dp);
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d %d", &n, &m, &k);
    printf("%d\n", F(n, m, k));
  }
  return 0;
}
