They Are Bored
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 13 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Zhxfl is good at graph theory, and he always has to draw some points on the paper and connects them.
But this time, he suffers a NP problem that no matter how he thinks, he can't solve it. He is in bad mood, and he connects all pairs of points on the paper without purpose.
But as a teammate, what Biaoshao could do is just to draw some points on the paper and let Zhxfl to connect them with straight line.
Please see the following description to realize what kind of points Biaoshao will draw. (So boring they are!)
A point (x, y) in the Cartesian plane is considered to be an integer point, if and only if x and y are both integers.
For a pair of given integers m and n, we define a empty point set S initially. Then all the integer points (x, y) which meets the condition that 0<=x<=m and 0<=y<=n should be added to S.
For each pair of integer points (the two points are different) in S, Zhxfl should draw a straight line across them. Zhxfl wants to know how many straight lines that he will have to draw at least for all pairs of integer points in S. Could you help poor Zhxfl?
But this time, he suffers a NP problem that no matter how he thinks, he can't solve it. He is in bad mood, and he connects all pairs of points on the paper without purpose.
But as a teammate, what Biaoshao could do is just to draw some points on the paper and let Zhxfl to connect them with straight line.
Please see the following description to realize what kind of points Biaoshao will draw. (So boring they are!)
A point (x, y) in the Cartesian plane is considered to be an integer point, if and only if x and y are both integers.
For a pair of given integers m and n, we define a empty point set S initially. Then all the integer points (x, y) which meets the condition that 0<=x<=m and 0<=y<=n should be added to S.
For each pair of integer points (the two points are different) in S, Zhxfl should draw a straight line across them. Zhxfl wants to know how many straight lines that he will have to draw at least for all pairs of integer points in S. Could you help poor Zhxfl?
Input
There are multiple test cases. The first line contains an integer T (T<=30), indicating the number of test cases.
Then T lines follow, each line contains two integers m and n. (0<m,n<=3000).
Then T lines follow, each line contains two integers m and n. (0<m,n<=3000).
Output
For each test case, output "Case #D: " first, D is the test case number.
Then calculate the number of straight lines that Zhxfl will have to draw at least and output this number.
Then calculate the number of straight lines that Zhxfl will have to draw at least and output this number.
Sample Input
2 2 2 3 3
Sample Output
Case #1: 20 Case #2: 62
Source
华南师范大学·2012年ACM程序设计竞赛·决赛