HackerEarth has decided to give exciting gifts to the contingents that have come.
They have decided to pack gifts for each member in cube boxes. HackerEarth 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.

HackerEarth wants to know the minimum possible volume of the box B which can store their gifts.

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

SAMPLE INPUT
2
2 2 2
19 1 2

SAMPLE OUTPUT
20
27

Explanation

Case #1: The required dimension is 2x2x5
Case #2: The required dimension is 3x3x3

见题面

见题面