一个模拟题啊。

观察到 $n,m,k$ 很小，因此我们可以考虑预处理每种答案。

考虑如何预处理，我们可以先找一个中心，然后逐渐往外部扩展，可以搜出所有情况，记得要加个旋转系统来判重。

注意及时剪枝，不然会 TLE，我的代码通过 hash 判重的方式剪枝。

#include<bits/stdc++.h>
using namespace std;
#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define forll(i,a,b,c) for(register long long i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(register long long i=a;i>=b;i-=c)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define mid ((l+r)>>1)
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define ll long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
ll t,n;
ll dx[]={0,0,1,-1},dy[]={1,-1,0,0},ans;
ll sum[20][20][20];
char a[50][50],c[50][50];
ll Base1=23,Base2=1;
ll mod1=232332333,mod2=1;
map<ll,map<ll,ll>>mp[20];
ll HASH1(ll x,ll y,ll xx,ll yy)
{
	ll sum=0;
	forl(i,x,xx)
		forl(j,y,yy)
			sum*=Base1,sum+=c[i][j]*(i-x+1)*(j-y+1),sum%=mod1;
	return sum;
}
ll HASH2(ll x,ll y,ll xx,ll yy)
{
	ll sum=0;
	forl(i,x,xx)
		forl(j,y,yy)
			sum*=Base2,sum+=c[i][j]*(i-x+1)*(j-y+1),sum%=mod2;
	return sum;
}
void f(ll xxx)
{
	ll x=1e18,y=1e18,xx=0,yy=0;
	forl(i,0,21)
		forl(j,0,21)
			if(a[i][j]=='#')
				x=min(x,i),y=min(y,j),xx=max(xx,i),yy=max(yy,j);
	ll mi=min(xx-x+1,yy-y+1),ma=max(xx-x+1,yy-y+1);
	sum[mi][ma][xxx]++;
}
bool check(ll _1)
{
	forl(i,0,21)
		forl(j,0,21)
			c[i][j]='.';
	ll x=1e18,y=1e18,xx=0,yy=0;
	forl(i,0,21)
		forl(j,0,21)
			if(a[i][j]=='#')
				x=min(x,i),y=min(y,j),xx=max(xx,i),yy=max(yy,j);
	forl(i,x,xx)
		forl(j,y,yy)
			c[i][j]=a[i][j];
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/

	if(mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)])
		return 0;
	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/

	forl(i,x,xx)
		forl(j,y,y+(yy-y)/2)
			swap(c[i][j],c[i][yy-(j-y)]);
	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/

	forl(i,x,xx)
		forl(j,y,y+(yy-y)/2)
			swap(c[i][j],c[i][yy-(j-y)]);
	forl(i,x,x+(xx-x)/2)
		forl(j,y,yy)
			swap(c[i][j],c[xx-(i-x)][j]);
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/
	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;

	forl(i,x,xx)
		forl(j,y,y+(yy-y)/2)
			swap(c[i][j],c[i][yy-(j-y)]);
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/
	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;
	
	forl(i,x,x+(xx-x)/2)
		forl(j,y,yy)
			swap(c[i][j],c[xx-(i-x)][j]);
	forl(i,x,xx)
		forl(j,y,y+(yy-y)/2)
			swap(c[i][j],c[i][yy-(j-y)]);
			
	forl(i,0,21)
		forl(j,i,21)
			swap(c[i][j],c[j][i]);
	
	x=1e18,y=1e18,xx=0,yy=0;
	forl(i,0,21)
		forl(j,0,21)
			if(c[i][j]=='#')
				x=min(x,i),y=min(y,j),xx=max(xx,i),yy=max(yy,j);
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/

	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/

	forl(i,x,xx)
		forl(j,y,y+(yy-y)/2)
			swap(c[i][j],c[i][yy-(j-y)]);
	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/

	forl(i,x,xx)
		forl(j,y,y+(yy-y)/2)
			swap(c[i][j],c[i][yy-(j-y)]);
	forl(i,x,x+(xx-x)/2)
		forl(j,y,yy)
			swap(c[i][j],c[xx-(i-x)][j]);
/*  forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/
	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;

	forl(i,x,xx)
		forl(j,y,y+(yy-y)/2)
			swap(c[i][j],c[i][yy-(j-y)]);
/*	forl(i,x,xx)
	{
		forl(j,y,yy)
			cout<<c[i][j];
		cout<<endl;
	}
	cout<<endl;*/
	mp[_1][HASH1(x,y,xx,yy)][HASH2(x,y,xx,yy)]=1;	
	return 1;
}
void dfs(ll x,ll y,ll sum)
{
	if(!check(n))
		return ;
	if(sum==n)
	{
	/*	forl(i,0,21)
		{
			forl(j,0,21)
				cout<<a[i][j];
			cout<<endl;
		}*/
		f(n);	
	//	ans++;
		return ;
	}
	forl(i,0,21)
	{
		forl(j,0,21)
		{
			if(a[i][j]=='#')
			{
				forl(k,0,3)
				{
					ll fx=i+dx[k],fy=j+dy[k];
					if(a[fx][fy]=='.')
					{
						a[fx][fy]='#';
						dfs(fx,fy,sum+1);
						a[fx][fy]='.';
					}
				}
			 } 
		}
	}
}
void sol(ll x)
{
	n=x;
	forl(i,0,21)
		forl(j,0,21)
			a[i][j]='.';
	a[11][11]='#';
	dfs(11,11,1);
}
void init()
{
	forl(i,1,10)
		sol(i);
}
void solve()
{
	ll n,m,k;
	cin>>k>>n>>m;
	ll ans=0;
	if(n>m)
		swap(n,m);
	forl(i,1,n)
		forl(j,1,m)
			ans+=sum[i][j][k];
	cout<<ans<<endl;	
}
int main()
{
	init();
	IOS;
	t=1;
	cin>>t;
	while(t--)
		solve();
	QwQ;
}