Jumping in the City

发布时间: 2017年12月10日 22:14   最后更新: 2017年12月10日 22:19   时间限制: 1000ms   内存限制: 512M

The god of the computer came to a beautiful city, GM city. The city can be regarded as a rectangle, which is divided into N*M areas. The top left corner is (1,1) while the lower right corner is (N,M). And the y-th column of the x-th row is denoted as (x, y). The god has a special ability to jump S areas horizontally or vertically from (x, y), that is, jumps from (x, y) to (x, y+S), (x,y-S), (x+S, y), (x-S, y), without exceeding the bounds. The god of computer can choose a starting area (x, y), and then make any number of jumps, but he cannot jump out of the city. Now he wants to select a starting area so that he can get to the largest number of different areas. And he wants to ask you how many of the starting areas allow the largest number of areas to reach. 

In the first line there is an integer T (T<=1000), which indicates the number of test cases.
In the next T lines there are three integers N, M and S (1<=N,M,S<=10^6).

Print T lines, on the i-th line print one integer – the answer for i-th test case.

2 3 1000000
3 3 2

For the first sample case, all the 6 areas can be the answer.

For the second sample case, 4 areas (1,1),(1,3),(3,1),(3,3) can be the answer.

2017 fdu-icpc

2017 Fudan ACM-ICPC 程序设计校赛现场赛