Description

The city where Tianyi lives is like an infinitely large Manhattan. If we place the city map on a Cartesian coordinate system, any integer point $(x,y)$ represents an intersection. Tianyi's doorstep intersection is at $(0,0)$, and she needs to start from here and reach the intersection $(a,b)$ of the studio as soon as possible. Every minute, Tianyi can move from her current intersection $(x,y)$ to $(x+1,y)$, $(x-1,y)$, $(x,y+1)$, or $(x,y-1)$.

But why would Tianyi walk to work? She has a very fast and mysterious broken bicycle! With it, Tianyi can instantly charge from $(x,y)$ to any one of the four positions $(x+l,y)$, $(x,y+l)$, $(x-l,y)$, $(x,y-l)$, without spending any time. However, to prevent the broken bicycle from falling apart, Tianyi can only use it up to $k$ times.

So, with the help of the broken bicycle, what is the minimum time Tianyi needs to travel from $(0,0)$ to $(a,b)$?

Due to the frequent moving of the studio, there are multiple test cases.

Input Format

The first line of the input contains an integer $T$ — the number of test cases.

The only line of each test case contains four intergers $a,b,k,l$ — the x,y coordinates of the intersection where the studio is located, the usage limit of the bicycle, and the charging distance of the bicycle.

Output Format

For each test case, output a single integer — the minimum time Tianyi needs to travel from $(0,0)$ to $(a,b)$.

3
4 5 3 2
1 1 4 5
8 8 4 8

3
2
0

Hint

Sample Explanation

We use $>$ to represent charging, and $\to$ to represent walking.

For the first test case, a possible moving way is: $(0,0)>(2,0)\to(3,0)\to(4,0)\to(4,1)>(4,3)>(4,5)$.

For the second test case, a possible moving way is: $(0,0)\to(0,1)\to(1,1)$.

For the third test case, a possible moving way is: $(0,0)>(0,8)>(8,8)$.

Constraints

Subtasks applied. You can only gain the score of the subtask if you accepted all the tests in the subtask.

For all tests, it is guaranteed that $1 \leq T \leq 10^5$，$0 \leq a,b,k,l\leq 10^{9}$.