FOC has decided to give Varchas goodies to the contingents that have come.
They have decided to pack goodies for each member in cube boxes. FOC has m cubes with edge length a (for top performers :D) and n cube shaped boxes with edge length 1 (for rest of the members).

They want to pack these boxes into a big cuboid box B. Also each cube shaped box should be packed each of its edges is parallel to an edge of the box B.

FOC wants to know the** minimum** possible volume of the box B which can store their boxes.

Note:

• The answer will fit in 32-bit signed integer.

Input:

The first line of the input contains an integer T denoting the number of test cases. Then, T lines follow.

Every line contains three space separated integers n, m and a.

Output:

For each test case, output a single integer containing the answer to the corresponding test case.

Constraints

• 1 <= T <= 10
• 1 <= n <= 10^9
• 1 <= m <= 10^6
• 2 <= a <= 10