This morning Aunt Petunia baked a cake. The cake had the shape of a box with dimensions A × B × C centimeters.
During the day, each of the D kids in the neighborhood stopped by for a slice of the cake. Every time a kid came for some cake, Aunt Petunia took her knife and made a single cut parallel to one of the sides of the cake. The piece she cut off the cake was always exactly 1 cm thick.
Problem specification
Given the values A, B, C, and D, compute the largest possible volume the cake could have at the end of the day.
Input specification
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line containing the integers A, B, C, and D.
You may assume that 0 < A,B,C ≤ 1018 and 0 ≤ D ≤ A + B + C − 3.
In the easy input you may assume that A,B,C ≤ 1000.
Output specification
For each test case output a single line with a single integer: the largest possible volume of the rest of the cake, after each of the kids got a slice.
You may assume that for each test case the answer will conveniently fit into a 64-bit signed integer variable.
Example
One way of optimally solving the second test case: first make two cuts parallel to the 4 × 5 side to obtain a 4×5×4 cake, and then make a cut parallel to the current 4×4 side to obtain a cube with side 4 cm long.