#include <bits/stdc++.h>
std::ostream& OUT = std::cout;
std::istream& IN = std::cin;
int r[31][31][51];
int Sqr(int a) { return a * a; }
int R(int n, int m, int k) {
  if (k == 0) return 0;
  if (r[n][m][k] != -1) return r[n][m][k];
  if (k < n && k < m) return r[n][m][k] = r[m][n][k] = Sqr(std::min(n, m)) + 1;
  int nm = n * m;
  if (nm == k) return r[n][m][k] = r[m][n][k] = 0;
  int best = INT_MAX;
  int rrr = n == m ? 1 : 2;
  for (int o = 0; o < rrr; ++o) {
    int nn = n * n;
    for (int i = 1, c = n; c <= k; c += n, ++i) {
      int rr = nn + R(n, m - i, k - c);
      if (rr < best) best = rr;
    }
    for (int i = m - 1; n * i >= k; --i) {
      int rr = nn + R(n, i, k);
      if (rr < best) best = rr;
    }
    std::swap(n, m);
  }
  return r[n][m][k] = r[m][n][k] = best;
}
int main() {
  for (int i = 0; i < 31; ++i)
    for (int j = 0; j < 31; ++j)
      for (int k = 0; k < 51; ++k) r[i][j][k] = -1;
  for (int i = 1; i < 31; ++i) {
    for (int k = 1; k < i; ++k) r[i][1][k] = r[1][i][k] = 1;
    r[i][1][i] = r[1][i][i] = 0;
  }
  int t;
  IN >> t;
  for (int i = 0; i < t; ++i) {
    int n, m, k;
    IN >> n >> m >> k;
    OUT << R(n, m, k) << '\n';
  }
}
