407527: GYM102822 H Hide and Seek

Little Rabbit and Little Horse are playing hide and seek on a plane that can be described by Cartesian coordinates. Little Horse is the hider and Little Rabbit is the seeker. Little Rabbit is eager to win, so he decides to cheat. He prepared three locating devices, placing one at $$$(0,0)$$$, one on Little Horse, and one on himself. These devices cannot show accurate coordinates but can show the Manhattan distance between every two devices.

The Manhattan distance is the sum of the lengths of the projections of the line segment between the points onto the coordinate axes. For example, the Manhattan distance between $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$|x_1-x_2|+|y_1-y_2|$$$. That is to say, if Little Rabbit is at $$$(x_1,y_1)$$$, and Little Horse is at $$$(x_2,y_2)$$$, then Little Rabbit's devices will show $$$d_{01}=|x_1|+|y_1|$$$, $$$d_{02}=|x_2|+|y_2|$$$ and $$$d_{12}=|x_1-x_2|+|y_1-y_2|$$$.

After getting these data, it's much easier for Little Rabbit to find Little Horse. But Little Rabbit wants to know that if their coordinates are integers, how many different situations of their locations there are. Please note that when $$$(x_1,y_1) \neq (x_2,y_2)$$$, Little Rabbit at $$$(x_1,y_1)$$$ and Little Horse at $$$(x_2,y_2)$$$ is a different situation from Little Rabbit at $$$(x_2,y_2)$$$ and Little Horse at $$$(x_1,y_1)$$$. It's also possible that Little Rabbit and Little Horse are at the same point.

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.

Each test case contains three integers $$$d_{01},d_{02},d_{12}$$$ ($$$0 \le d_{01},d_{02},d_{12} \le 10^9$$$), the meanings of which are given above.

For the $$$x$$$-th test case, if the answer is $$$y$$$, output $$$Case$$$ #$$$x$$$: $$$y$$$ in a single line.

4
2 4 2
1 3 2
3 4 5
1 1 1

Case #1: 32
Case #2: 20
Case #3: 48
Case #4: 0