Construct Rectangle Solution

Construct Rectangle

Prepbuddy came to visit his friend and noticed that his friend owns an incredibly beautiful rectangle with sides XX and YY. Prepbuddy realized that he had always dreamed about a rectangle of such an area.

After returning to his home Prepbuddy has found out that he has a lot of squares of size C×CC×C. He would like to construct a rectangle out of such squares that would have the area as close as possible to the area of his friend’s rectangle. He wants to minimize the absolute difference between his rectangle’s area and his friend’s rectangle’s area. Prepbuddy would put squares with sides parallel to each other without gaps and overlapping. He would use at least one square.

For example, if his friend has 4×54×5 rectangle and he has 3×33×3 squares, the rectangle with the closest area to his friend rectangle, that Prepbuddy can construct is 3×63×6.

Input Format

The first line contains the number of test cases TT. The first line of each test case contains three integers XX, YY, and CC.

Output Format

For each test print the area of the rectangle that Prepbuddy would construct out of his squares, that has the closest possible area to his friend’s rectangle.

If there are several possible optimal answers, output anyone.

Constraints

1≤T≤100001≤T≤10000 1≤X,Y,C≤1091≤X,Y,C≤109

Time Limit

2 second

Example

Sample Input

3 4 5 3 2 3 1 6 4 5

Sample Output

18 6 25

Note : Please click on 1 or 2 ads to help us run this site and encourages us to provide you the solutions.

JULY 2021 CODING MARATHON

Leave a Comment