#OJ1552. )
)
)
Time Limit: 1 Sec Memory Limit: 256 MB
Description
猴哥厌烦了在一条直线上跳格子,于是他发明了一个新的游戏——在矩阵中跳格子。这个矩阵有n行m列,猴哥只能垂直或水平跳跃,每次跳k格,并且不能离开这个矩阵:即他能从(x, y)跳到(x+k,y)或者(x-k,y)或者(x,y+k)或者(x,y-k)。 因为他每次只能跳跃k格,所以他无法访问这个矩阵中的所有格子。现在他想访问尽量多的格子,所以他必须从一些特殊的位置开始跳跃。 现在的问题是有多少个特殊位置,使猴哥从这些位置开始跳跃可以访问尽量多的格子。
Input
第一行输入一个T 代表有T组样例。 每组样例有三个数n,m,k (0< n,m,k <= 10^6)。
Output
对于每组样例,输出样例编号及特殊位置个数。
Sample Input
2
2 3 100
3 3 2
Sample Output
Case 1: 6
Case 2: 4