题目背景

某个夏天，18071 号工作室的 staff 集体转业了。辗转至年末，天依终于在 40312 号工作室拉到了合作。但是……看着编号的差距，按时到班可不是一件容易的事情。

七点半，闹铃声响起，早高峰即将迎接起床气！

题目描述

天依住在的城市像一个无穷大的曼哈顿。如果把城市地图放在平面直角坐标系中，任何一个整点 $(x,y)$ 都是一个十字路口。天依家门口的十字路口为 $(0,0)$，天依需要从这里出发，尽快抵达工作室所在的十字路口 $(a,b)$。每分钟，天依可以从她所在的十字路口 $(x,y)$ 移动至 $(x+1,y)$，$(x-1,y)$，$(x,y+1)$ 或者 $(x,y-1)$。

天依怎么会走路上班呢？她可以使用一辆很快很邪门的破自行车！骑上它，天依可以从 $(x,y)$ 瞬间冲到 $(x+l,y)$，$(x,y+l)$，$(x-l,y)$，$(x,y-l)$ 四个位置中的一个，不花费任何时间。但为了避免破自行车散架，天依最多使用 $k$ 次自行车。

那么，在破自行车的助力下，天依至少需要多少时间才能从 $(0,0)$ 出发到达 $(a,b)$ 呢?

因为工作室经常搬家，所以有多组测试数据。

输入格式

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行四个整数 $a,b,k,l$，分别表示工作室所在的十字路口的横纵坐标，自行车的使用次数限制和自行车的移动距离。

输出格式

输出 $T$ 行，第 $i$ 行一个整数，表示第 $i$ 组数据中到达工作室的最小时间。

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

3
2
0

提示

样例解释：

我们使用 $>$ 表示猛冲，$\to$ 表示行走。

对于样例一，一种可能的移动方式是：$(0,0)>(2,0)\to(3,0)\to(4,0)\to(4,1)>(4,3)>(4,5)$。

对于样例二，一种可能的移动方式是：$(0,0)\to(0,1)\to(1,1)$。

对于样例三，一种可能的移动方式是：$(0,0)>(0,8)>(8,8)$。

数据规模与约定

本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。

对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$0 \leq a,b,k,l\leq 10^{9}$。

对于不同的子任务，作如下约定：