#include <bits/stdc++.h>
#pragma warning(error : 4700)
#pragma warning(error : 4715)
#pragma warning(error : 4716)
using namespace std;
const long long MILLER_RABIN = 3215031751;
const long double PI = 3.14159265358979323846;
inline int lg2(long long n) {
  int h = 0;
  while ((1ll << h) < n) ++h;
  return h;
}
struct config_io {
  config_io() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
  }
} cnf_io;
struct config_rand {
  config_rand() {
    srand(chrono::duration_cast<chrono::nanoseconds>(
              chrono::high_resolution_clock::now().time_since_epoch())
              .count());
  }
} cnf_rand;
namespace std {
template <>
struct hash<pair<int, int> > {
  size_t operator()(const pair<int, int> &x) const {
    return (x.first * 31 + x.second) % ((int)1e9 + 7);
  }
};
}  // namespace std
inline int ord(char ch) {
  if (ch >= 'a' && ch <= 'z') {
    return int(ch - 'a') + 1;
  }
  if (ch >= 'A' && ch <= 'Z') {
    return int(ch - 'A') + 27;
  }
  throw "";
}
inline void scan(int &x) { scanf("%d", &x); }
inline void scan(int &x, int &y) { scanf("%d%d", &x, &y); }
inline void scan(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
inline void print(const int &x) { printf("%d\n", x); }
inline void print(const int &x, const int &y) { printf("%d %d\n", x, y); }
int mem[32][32][52];
int go(int n, int m, int k) {
  if (mem[n][m][k] != -1) {
    return mem[n][m][k];
  }
  if (k == 0) return mem[n][m][k] = 0;
  if ((n == 1 && m == k) || (n == k && m == 1)) return mem[n][m][k] = 0;
  if (n * m == k) return mem[n][m][k] = 0;
  int ans = 1e9;
  for (int i = 1; i < n; ++i) {
    for (int kk = 0; kk <= k; ++kk) {
      ans = min(ans, go(i, m, kk) + m * m + go(n - i, m, k - kk));
    }
  }
  for (int i = 1; i < m; ++i) {
    for (int kk = 0; kk <= k; ++kk) {
      ans = min(ans, go(n, i, kk) + n * n + go(n, m - i, k - kk));
    }
  }
  return mem[n][m][k] = ans;
}
int main() {
  for (int i = 0; i < 32; ++i) {
    for (int j = 0; j < 32; ++j) {
      for (int k = 0; k < 52; ++k) {
        mem[i][j][k] = -1;
      }
    }
  }
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    int n, m, k;
    cin >> n >> m >> k;
    cout << go(n, m, k) << endl;
  }
  return 0;
}
