#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000002;
const long long INFLL = 100000000000000000ll;
const long long MOD = 1000000007;
int T;
long long DP2[32][32][905];
int main() {
  for (int a = (0); a <= (30); a++)
    for (int b = (0); b <= (30); b++)
      for (int c = (0); c <= (900); c++) DP2[a][b][c] = INFLL;
  for (int x = (1); x <= (30); x++)
    for (int y = (1); y <= (30); y++) DP2[x][y][0] = DP2[x][y][x * y] = 0;
  for (int x = (1); x <= (30); x++)
    for (int y = (1); y <= (30); y++)
      for (int k = (1); k <= (x * y); k++) {
        for (int x1 = (1); x1 <= (x - 1); x1++) {
          int x2 = x - x1;
          DP2[x][y][k] = min(DP2[x][y][k], DP2[x1][y][k] + y * y);
          DP2[x][y][k] = min(DP2[x][y][k], DP2[x2][y][k] + y * y);
          if (k >= x2 * y)
            DP2[x][y][k] = min(DP2[x][y][k], DP2[x1][y][k - x2 * y] + y * y);
          if (k >= x1 * y)
            DP2[x][y][k] = min(DP2[x][y][k], DP2[x2][y][k - x1 * y] + y * y);
        }
        for (int y1 = (1); y1 <= (y - 1); y1++) {
          int y2 = y - y1;
          DP2[x][y][k] = min(DP2[x][y][k], DP2[x][y1][k] + x * x);
          DP2[x][y][k] = min(DP2[x][y][k], DP2[x][y2][k] + x * x);
          if (k >= x * y2)
            DP2[x][y][k] = min(DP2[x][y][k], DP2[x][y1][k - x * y2] + x * x);
          if (k >= x * y1)
            DP2[x][y][k] = min(DP2[x][y][k], DP2[x][y2][k - x * y1] + x * x);
        }
      }
  cin >> T;
  while (T--) {
    int x, y, k;
    scanf("%d %d %d", &x, &y, &k);
    printf("%I64d\n", DP2[x][y][k]);
  }
}
