There are three jugs of volume a, b and c liters. The number a, b, and c are positive integers. The first and the second jug are empty initially, and the third one is completely filled with water. It is allowed to pour water from one jug into another until either the pouring jug is empty or the poured jug is full. This operation can be performed zero, one, or more times.
Compute the minimum number of water pouring operations to be performed so that one of the jugs contains d’ liters of water. The number d’ is a nonnegative integer, which is closest to but less than or equal to a given positive integer d.
The first line of input contains the number of test cases. In the next T lines, T test cases follow. Each test case is given in one line, containing four positive integers: a, b, c and d, 1 <= a, b, c, d <= 200.
The output consists of two integers separated by a single space. The first integer equals the least total amount (the sum of all waters you pour from one jug to another) of poured water. The second integer equals d, if d liters of water could be produced by such transformations, or equals the closest smaller value d' that your program has found.