Eating Pancakes

This morning, Eunjoo made a rectangular-box-shaped pancake. Its width, depth, and height are A cm, B cm, and C cm.

Shinhye will eat the pancake D times. Each time she eats, Eunjoo cuts the currently remaining pancake parallel to one of its faces and gives Shinhye exactly one slice of thickness 1 cm. Eunjoo may choose the cutting direction each time.

Eunjoo originally wanted to eat the whole pancake herself, so after Shinhye eats D times, she wants to leave as much pancake as possible.

Given A, B, C, and D, compute the maximum possible volume of pancake that Eunjoo can leave after Shinhye eats D times.

The first line contains the number of test cases T. Test cases may be separated by blank lines.

Each test case consists of one line containing A, B, C, and D.

For each test case, output one line containing the maximum volume of pancake Eunjoo can leave. This value fits in a signed 64-bit integer.

• 0 ≤ D ≤ A + B + C - 3

In the second test case, Eunjoo can first cut twice parallel to the 4 × 5 face, reducing the height from 6 cm to 4 cm. Then she can cut once more parallel to a 4 × 4 face. The remaining pancake is 4 × 4 × 4, so its volume is 64.