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.