天依住在的城市像一个无穷大的曼哈顿。如果把城市地图放在平面直角坐标系中，任何一个整点 $(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$，分别表示工作室所在的十字路口的横纵坐标，自行车的使用次数限制和自行车的移动距离。

样例解释：

我们使用 $>$ 表示猛冲，$\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\le T\le 10^5$，$0\le a,b,k,l\le 10^9$。

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

贪心、数学