#include <bits/stdc++.h> using namespace std; #define int long long const int mod=1004535809; int n,m,k; int a[5010][5010]; map<string,bool> mp; int ans; void dfs(int x,int y) { if(y>m) { dfs(x+1,1); return ; } if(x>n) { mp.clear(); for(int i=1;i<=n;i++) { string s=""; for(int j=1;j<=m;j++) s+=a[i][j]+'0'; if(mp.count(s)) return ; mp[s]=1; } mp.clear(); for(int j=1;j<=m;j++) { string s=""; for(int i=1;i<=n;i++) s+=a[i][j]+'0'; if(mp.count(s)) return ; mp[s]=1; } ans++; return ; } for(int i=1;i<=k;i++) { a[x][y]=i; dfs(x,y+1); } } signed main() { freopen("square.in","r",stdin); freopen("square.out","w",stdout); ios::sync_with_stdio(false); int T; cin>>T; while(T--) { cin>>n>>m>>k; ans=0; dfs(1,1); cout<<ans%mod<<endl; } return 0; }