NC24670. Machine Learning
描述
"You know? AI is ruling the world!" Well, there seems no wrong with it as well if you change the word "ruling" into "ruining".
Anyway, to make Ramen's program better, he wants to add machine learning technique into his project. He is working on a picture generation project, and the first step of the process is to calculate the sum of some rectangle of a very special matrix.
The matrix itself is easy to describe. Think about the first quadrant of a two-dimensional coordinate system, the value at the point (i,j) is:
%3D%5Ctext%7Bmax%7D(i%2Cj)%5C%20%5Ctext%7Bmod%7D%5C%204)
For example, here is a part of the matrix: 
It's the rectangle (0,0)-(1,1). The sum of it is 3.
Ramen has written a very fast program to calculate the sum of a rectangle. But after downloading the training data set, he realizes that there is a severe problem: in his program, the origin is (0,0), but all of the training data's origin is (1,1). He has no idea how to modify his program to suit the training data, can you help him to do it?
Anyway, to make Ramen's program better, he wants to add machine learning technique into his project. He is working on a picture generation project, and the first step of the process is to calculate the sum of some rectangle of a very special matrix.
The matrix itself is easy to describe. Think about the first quadrant of a two-dimensional coordinate system, the value at the point (i,j) is:
For example, here is a part of the matrix:
Then, Ramen needs the sum of some rectangles. We are using (x1,y1)-(x2,y2) to describe a rectangle, means that the lower left corner's coordinate is (x1, y1) while the upper right corner is (x2, y2). For example, under some situation, he needs the sum of the rectangle below:
It's the rectangle (0,0)-(1,1). The sum of it is 3.
Ramen has written a very fast program to calculate the sum of a rectangle. But after downloading the training data set, he realizes that there is a severe problem: in his program, the origin is (0,0), but all of the training data's origin is (1,1). He has no idea how to modify his program to suit the training data, can you help him to do it?
输入描述
The input contains multiple test cases.
The first line is an integer T(1 <= T <= 1000), which indicates the number of test cases. Then T lines follow.
Each of the next T lines contains four integers x1, x2, y1, y2 (1 <= x1 <= x2 <= 1e9, 1 <= y1 <= y2 <= 1e9), indicates the rectangle (x1,y1)-(x2,y2).
输出描述
For each test case, output Case #x: y, where x is the number of the test case (starts from 1) and y is the answer.
示例1
输入:
3 1 1 2 2 2 3 4 5 12 34 56 78
输出:
Case #1: 3 Case #2: 16 Case #3: 3039
说明:
Sample 1 is described in the statement. Because the origin is (1,1), the rectangle's coordinate is now (1,1)-(2,2).
For sample 2, the required rectangle is:
It's obvious the sum of them is 3x4+2x2=16.
It's obvious the sum of them is 3x4+2x2=16.