Round E - B(Birthday Cake)


#include <bits/stdc++.h>
using namespace std;
int cut(int length, unsigned long long K) {
	if(length%K == 0)
		return length/K;
	return length/K+1;
}
int main() {
	int T;
	scanf("%d", &T);
	
	for(int tc = 1; tc <= T; tc++) {
		int R, C;
		unsigned long long K;
		scanf("%d %d %llu", &R, &C, &K);
		int r1, c1, r2, c2;
		scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
		
		unsigned long long result = 0;
		if(r1 == 1 && c1 == 1 && r2 == R && c2 == C)
			result += 0;
		else if((r1 == 1 && c1 == 1 && r2 == R) || (r1 == 1 && r2 == R && c2 == C))
			result += cut(R, K);
		else if((r1 == 1 && c1 == 1 && c2 == C) || (c1 == 1 && r2 == R && c2 == C))
			result += cut(C, K);
		else if(r1 == 1 && r2 == R)
			result += 2*cut(R,K);
		else if(c1 == 1 && c2 == C)
			result += 2*cut(C,K);
		else if((r1 == 1 && c1 == 1) || (r1 == 1 && c2 == C) || (r2 == R && c2 == C) || (r2 == R && c1 == 1))
			result += cut((c2-c1+1),K) + cut((r2-r1+1),K);
		else if((r1 == 1) || (r2 == R))
			result += cut((c2-c1+1),K) + 2*cut((r2-r1+1),K);
		else if((c1 == 1) || (c2 == C))
			result += 2*cut((c2-c1+1),K) + cut((r2-r1+1),K);
		else {
			int temp;
			int mini = 1000000000;
			temp = cut(c2,K) + cut((c2-c1+1),K) + 2*cut((r2-r1+1),K);
			mini = temp < mini ? temp : mini;
			temp = cut((C-c1+1),K) + cut((c2-c1+1),K) + 2*cut((r2-r1+1),K);
			mini = temp < mini ? temp : mini;
			
			temp = cut(r2,K) + 2*cut((c2-c1+1),K) + cut((r2-r1+1),K);
			mini = temp < mini ? temp : mini;
			temp = cut((R-r1+1),K) + 2*cut((c2-c1+1),K) + cut((r2-r1+1),K);
			mini = temp < mini ? temp : mini;
			
			result += mini;
		}
		unsigned long long  W = c2-c1+1;
		unsigned long long  H = r2-r1+1;		
		unsigned long long wq = W/K;
		unsigned long long wr = W%K;
		unsigned long long hq = H/K;
		unsigned long long hr = H%K;
		if(wr == 0 && hr == 0)
			result += (wq-1)*hq + (hq-1)*wq;
		else if(wr == 0)
			result += (wq-1)*(hq+1)+hq*(wq-1);
		else if(hr == 0)
			result += (hq-1)*(wq+1)+wq*(hq-1);
		else
			result += wq*(hq+1) + hq*(wq+1);
		result += wq*hq*(K-1+K*(K-1));
		if(wr != 0)
			result += hq*(wr-1+wr*(K-1));
		if(hr != 0)
			result += wq*(hr-1+hr*(K-1));
		if(wr != 0 && hr != 0) {
			result += hr*wr-1;
		}
		printf("Case #%d: %llu\n", tc, result);
	}
}