Discovering Paths

/*
Case:
2
5 5 4
1 1 2 2
0 1 2 3
0 2 0 3
0 0 0 1
4 4 3
3 3 3 3
0 0 0 0
1 1 2 2

Output:
Case 1
   Query 1: 10
   Query 2: 5
   Query 3: 55
   Query 4: 0
Case 2
   Query 1: 0
   Query 2: 0
   Query 3: 2
*/

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

#define INF 1000000000
#define FOR(i, a, b) for(int i=int(a); i<int(b); i++)
#define FORC(cont, it) for(decltype((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define maxSize 1001
#define MOD 912

ii mat[maxSize][maxSize], ans[maxSize][maxSize];

int main() {
	int T, R, C, Q, a, b, c,d, caso=1;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &R, &C, &Q);
		printf("Case %d\n", caso++);
		memset(mat, 0, sizeof(mat));
		mat[R-1][C-1].second = mat[0][0].first = 1;
		//First is how many ways to reach this square from start position, second how many ways to reach end from here
		FOR(i, 0, R) {
			FOR(j, 0, C) {
				if (i) mat[i][j].first += mat[i - 1][j].first, mat[R - i - 1][C - j - 1].second += mat[R - i][C - j - 1].second;
				if (j) mat[i][j].first += mat[i][j - 1].first, mat[R - i - 1][C - j - 1].second += mat[R - i - 1][C - j].second;
				mat[i][j].first %= MOD, mat[R - i - 1][C - j - 1].second %= MOD;
			}
		}
		//First is rows, second columns
		FOR(i, 0, R) {
			FOR(j, 0, C) {
				ans[i + 1][j + 1].first = (mat[i][j].first*mat[i + 1][j].second + ans[i + 1][j].first) % MOD;
				ans[i + 1][j + 1].second = (mat[i][j].first*mat[i][j + 1].second + ans[i][j + 1].second) % MOD;
			}
		}
		FOR(i,1,Q+1) {
			scanf("%d %d %d %d", &a, &b, &c, &d);
			int aa = (ans[a][d + 1].first - ans[a][b].first + ans[c + 1][b].second - ans[a][b].second + 2 * MOD) % MOD;
			if (!a&&!b) aa = mat[0][0].second;
			printf("   Query %d: %d\n", i, (mat[0][0].second - aa + MOD) % MOD);
		}
	}
	return 0;
}