```#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL x[1000*1005];
struct node{
LL u, v, w;
};
int f[1000*1005*2];
int fd(int x){
if(f[x]==-1) return x;
return f[x]=fd(f[x]);
}
vector<node> v[10005];
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}

int main(){

int T, cas=1; scanf("%d", &T);
while(T--){
for(int i=0; i<=10000; i++) {
v[i].clear();//必须先加这一句，否则直接用v.shrink_to_fit(),无法释放内存
v[i].shrink_to_fit();
}
LL N, M, Sr, Sc, Tr, Tc;
LL x1, x2, A, B, C, P;
f[1]=f[2]=-1;
for(int i=3; i<=N*M; ++i){
x[i]=(A*x[i-1]+B*x[i-2]+C)%P;
f[i]=-1;
}
for(int i=1; i<=N; ++i){
for(int j=1; j<=M; ++j){
if(i+1<=N){
int s = (i-1)*M + j;
int t = i*M + j;
v[x[s]*x[t]].push_back({s, t});
}
if(j+1<=M){
int s = (i-1)*M + j;
int t = (i-1)*M+j+1;
v[x[s]*x[t]].push_back({s, t});
}
}
}
LL ans=0, now=N*M-1;
for(int i=10000; i>=0&&now>0; i--){
for(auto To: v[i]){
int x=fd(To.u), y=fd(To.v);
if(x!=y){
ans+=i;
f[x]=y;
--now;
}
}
}
printf("Case #%d: %lld\n", cas++, ans);
}

return 0;
}```