#include <bits/stdc++.h>
using namespace std;
template <typename T>
void pr(vector<T> &v) {
  for (int i = 0; i < (int)(v).size(); i++) cout << v[i] << " ";
  cout << '\n';
  ;
}
template <typename T>
void pr(vector<vector<T>> &v) {
  for (int i = 0; i < (int)(v).size(); i++) {
    pr(v[i]);
  }
}
template <typename T>
void re(T &x) {
  cin >> x;
}
template <typename T>
void re(vector<T> &a) {
  for (int i = 0; i < (int)(a).size(); i++) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &...rest) {
  re(first);
  re(rest...);
}
template <typename T>
void pr(T x) {
  cout << x << '\n';
  ;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &...rest) {
  cout << first << " ";
  pr(rest...);
  cout << '\n';
  ;
}
void ps() {
  cout << '\n';
  ;
}
template <class T, class... Ts>
void ps(const T &t, const Ts &...ts) {
  cout << t;
  if (sizeof...(ts)) cout << " ";
  ps(ts...);
}
const long long MOD = 998244353;
long double PI = 4 * atan(1);
long double eps = 1e-12;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long dp[35][35][60] = {};
  for (int i = 0; i < 35; i++) {
    for (int j = 0; j < 35; j++) {
      for (int k = 1; k < 60; k++) {
        dp[i][j][k] = MOD;
      }
      if (i * j < 60) {
        dp[i][j][i * j] = 0;
      }
    }
  }
  dp[1][1][1] = 0;
  for (int size = 1; size < 51; size++) {
    for (int r = 1; r < 31; r++) {
      for (int c = 1; c < 31; c++) {
        if (size <= r * c) {
          for (int rcut = 1; rcut < r; rcut++) {
            if (rcut * c <= size) {
              dp[r][c][size] =
                  min(dp[r][c][size], c * c + dp[r - rcut][c][size - rcut * c]);
            }
            dp[r][c][size] = min(dp[r][c][size], c * c + dp[r - rcut][c][size]);
          }
          for (int ccut = 1; ccut < c; ccut++) {
            if (ccut * r <= size) {
              dp[r][c][size] =
                  min(dp[r][c][size], r * r + dp[r][c - ccut][size - r * ccut]);
            }
            dp[r][c][size] = min(dp[r][c][size], r * r + dp[r][c - ccut][size]);
          }
        }
      }
    }
  }
  int tcase;
  cin >> tcase;
  while (tcase--) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << dp[n][m][k] << '\n';
    ;
  }
}
