Server Time: Wed Feb 26, 2020 2:11 pm
Welcome ( logout
G - Pair of Touching Circles
PDF (English) Ranklist
Time Limit: 3 second(s) Memory Limit: 32 MB

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 he also wants their centers on integer coordinates and their radii to 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.



The first line of input contains the number of test cases T (T500). Each of the next T lines will contain two integers H and W (0 < H, W1000).



For each line of input output the case number and the number of ways of drawing such pairs of circles maintaining the mentioned constraints. See sample output for exact formatting. The output will fit into 64-bit signed integer.


Sample Input                               Output for Sample Input

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

Illustration of case 3:


Problem Setter: Md. Towhidul Islam Talukder
Special Thanks: Md. Arifuzzaman Arif, Jane Alam Jan
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan