Rectangle and Squares

Time limit2sMemory limit512 MB

Summary

Given target area A*B and a square size C, find the rectangle of side C that is closest in area to A*B, breaking ties toward the smaller area.

Level: Medium6 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

Elijah visited his friend Phil and saw a rectangle with sides $A$ and $B$ . Elijah had wanted a rectangle of that area for a long time.

Back home, Elijah found that he owns a large number of squares of size $C \times C$ . He wants to build a rectangle out of those squares whose area is as close as possible to the area of Phil's rectangle. In other words, he wants to minimize the absolute difference between the two areas.

Elijah puts the squares down with their sides parallel, without gaps and without overlaps. He uses at least one square.

For example, if Phil's rectangle is $4 \times 5$ and Elijah's squares are $3 \times 3$ , the rectangle with the closest area that Elijah can build is $3 \times 6$ .

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 10\,000$ ).

Each of the next $t$ lines contains three integers $A$ , $B$ and $C$ ( $1 \le A, B, C \le 10^9$ ).

Output

For each test case print one line with the area of the rectangle Elijah builds.

If several areas are equally close to the area of Phil's rectangle, print the smallest of them.

Examples3

Example 1
Input
```
3
4 5 3
2 3 1
6 4 5
```
Expected output
```
18
6
25
```
Example 2
Input
```
1
1 1 1
```
Expected output
```
1
```

Example 3

Input

Expected output