You are given a rectangular grid of height H and width W. A problem setter wants to draw a pair of circles inside the rectangle so that they touch each other but do not share common area and both the circles are completely inside the rectangle.
As the problem setter does not like precision problems, he also wants their centers to be on integer coordinates and their radii should be positive integers as well.
How many different ways can he draw such pair of circles? Two drawings are different from each other if any of the circles has different center location or radius.
Input
Input starts with an integer T (≤ 500), denoting the number of test cases.
Each case starts with a line containing two integers H and W (0 < H, W ≤ 1000).
Output
For each case, print the case number and the number of ways of drawing such pairs of circles maintaining the mentioned constraints. Each output will fit into a 64-bit signed integer.
Sample
| Sample Input | Sample Output |
|---|---|
5 4 2 4 3 4 4 4 6 10 10 | Case 1: 1 Case 2: 2 Case 3: 6 Case 4: 16 Case 5: 496 |
Notes
For case 3, the possible results are:
