Bicycle Assisted Manhattan Navigation

Tianyi lives in an infinite Manhattan grid. In this grid, every integer coordinate (x, y) is an intersection. Her home is located at (0, 0) and her studio is at (a, b). Every minute, she can walk from her current intersection (x, y) to one of (x+1, y), (x-1, y), (x, y+1), or (x, y-1).

Luckily, she has a quirky bicycle. With the bicycle, she can instantly (in 0 minutes) move from (x, y) to one of the intersections (x+l, y), (x-l, y), (x, y+l), or (x, y-l). However, to prevent the bicycle from breaking apart, she can only use this bicycle move at most k times.

Your task is to determine the minimum time (in minutes) needed for Tianyi to travel from (0, 0) to (a, b) using walking (which takes 1 minute per step) and up to k bicycle moves.

Note: A bicycle move always moves exactly l units along one of the cardinal directions. It is allowed to overshoot the target coordinate on an axis, but then the extra distance must be compensated by additional walking moves.

Mathematically, if we denote d_x=|a| and d_y=|b|, and if Tianyi uses r bicycle moves along the x-axis and s bicycle moves along the y-axis (with r+s ≤ k), then she must cover a remaining walking distance of

[ |d_x - r\cdot l| + |d_y - s\cdot l| ]

Your goal is to choose non-negative integers r and s (with r+s ≤ k) such that the above expression is minimized.

inputFormat

The first line contains a single integer T, representing the number of test cases.

Each of the next T lines contains four integers a, b, l, k separated by spaces:

• a and b: the coordinates of the studio (-10⁹ ≤ a, b ≤ 10⁹),
• l: the fixed distance of each bicycle move, and
• k: the maximum number of bicycle moves available.

outputFormat

For each test case, output a single line with the minimum time (in minutes) required for Tianyi to reach (a, b) from (0,0).

sample

3
5 5 3 2
10 1 4 3
2 6 5 1

4
3
3