#include <bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
int memo[40][40][1000];

int dp(int n, int m, int k){
    if(memo[n][m][k]<INF) return memo[n][m][k];
    if(k==n*m || k==0) return memo[n][m][k]=0;
    else if(k>m*n) return memo[n][m][k]=INF/2;
    else {
        int h=INF,v=INF;
        for(int i=1; i<=n-1; i++){
            for(int j=0; j<=k; j++){
                int a;
                a=dp(n-i,m,k-j)+dp(i,m,j)+m*m;
                h=min(h,a);
            }
        }
        for(int i=1; i<=m-1; i++){
            for(int j=0; j<=k; j++){
                int b;
                b=dp(n,m-i,k-j)+dp(n,i,j)+n*n;
                v=min(v,b);
            }
        }
        return memo[n][m][k]=min(h,v);
    }
}

int main(){

    int t,n,m,k;
    memset(memo,63, sizeof(memo));
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>n>>m>>k;
        printf("%d\n", dp(n,m,k));
    }
    return 0;
}