#include <bits/stdc++.h>
using namespace std;
const int MAXINT = 1073741823;
const int MAXN = 31;
const int MAXSIZE = 51;
int answer[MAXN][MAXN][MAXSIZE];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t, n, m, k;
  cin >> t;
  for (int i = 1; i <= 30; i++) {
    for (int j = 1; j <= 30; j++) {
      for (int z = 1; z <= min(i * j, 50); z++) {
        answer[i][j][z] = MAXINT;
        if (i * j == z)
          answer[i][j][z] = 0;
        else {
          for (int a = 1; a <= i - 1; a++)
            for (int b = 0; b <= z; b++)
              if (j * a >= b && j * (i - a) >= z - b)
                answer[i][j][z] =
                    min(answer[i][j][z],
                        (j * j) + answer[a][j][b] + answer[i - a][j][z - b]);
          for (int a = 1; a <= j - 1; a++)
            for (int b = 0; b <= z; b++)
              if (i * a >= b && i * (j - a) >= z - b)
                answer[i][j][z] =
                    min(answer[i][j][z],
                        (i * i) + answer[i][a][b] + answer[i][j - a][z - b]);
        }
      }
    }
  }
  for (int q = 0; q < t; q++) {
    cin >> n >> m >> k;
    cout << answer[n][m][k] << '\n';
  }
  return 0;
}
