#include <bits/stdc++.h>
using namespace std;
const long long maxN = 3e1 + 17, N = 5e1 + 17, inf = 1e9 + 7, MOD = 1e9 + 7,
                Mod = 1e9 + 6;
long long n, m, y, t, d[maxN][maxN][N], help, mini, x;
int main() {
  for (long long i = 0; i <= 30; i++) {
    for (long long j = 0; j <= 30; j++) {
      for (long long k = 0; k <= 50; k++) d[i][j][k] = inf;
      if (i && j) d[i][j][0] = 0;
    }
  }
  for (long long i = 1; i <= 30; i++) {
    for (long long j = 1; j <= 30; j++) {
      mini = min((i * j), (long long)50);
      for (long long k = 1; k <= mini; k++) {
        if (i < 2 || j < 2) d[i][j][k] = 1;
        if (k == i * j) d[i][j][k] = 0;
        for (long long z = 0; z <= i; z++) {
          for (long long e = 0; e <= k; e++)
            d[i][j][k] =
                min(d[i][j][k], d[i - z][j][e] + d[z][j][k - e] + (j * j));
        }
        for (long long z = 0; z <= j; z++) {
          for (long long e = 0; e <= k; e++)
            d[i][j][k] =
                min(d[i][j][k], d[i][j - z][e] + d[i][z][k - e] + (i * i));
        }
      }
    }
  }
  cin >> t;
  for (long long i = 1; i <= t; i++) {
    cin >> n >> m >> y;
    cout << d[n][m][y] << "\n";
  }
  return cout << "\n", 0;
}
