蕾米莉亚试图逃跑,而灵梦则想要进行最后一击。
比赛场地包括 $$$n$$$ 位置排列成圆圈。对于每个 $$$1 \le i \lt n$$$,仓位 $$$i$$$ 和 $$$i+1$$$ 相邻,并且位置 $$$1$$$ 和 $$$n$$$ 也相邻。
最初,在时间 $$$0$$$,灵梦在位置 $$$x_1$$$ 并且 Remilia 位于位置 $$$x_2$$$,其中 $$$x_1 \ne x_2$$$。
每一秒,都会按顺序发生以下情况:
- 蕾米莉亚要么移动到相邻位置,要么留在原地。在整个游戏中,她最多可以移动到相邻位置 $$$k$$$ 次。
- 观察蕾米莉亚的动作后,灵梦要么移动到相邻位置,要么留在原地。
- 如果两次行动后他们处于同一位置,灵梦抓住蕾米莉亚,游戏结束。
假设两名玩家都发挥最佳状态,灵梦总是尝试最小化接球时间,而蕾米莉亚则尝试最大化它。
找出灵梦抓住蕾米莉亚之前的秒数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \let \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含四个整数 $$$n$$$, $$$x_1$$$, $$$x_2$$$ 和 $$$k$$$ ($$$2\le n\le10^8$$$, $$$1\le x_1,x_2\le n$$$, $$$x_1\ne x_2$$$, $$$0\le k\le 10^8$$$)。
输出
对于每个测试用例,假设两个玩家都处于最佳状态,输出灵梦抓住雷米莉亚之前的秒数。
示例
输入复制
42 1 2 04 3 2 14 2 3 116 8 4 2
输出复制
1226
注意
在第一个测试用例中,一个可能的操作顺序是:
- 第一秒,蕾米莉亚原地不动,然后灵梦移动到 $$$2$$$ 并抓住了雷米莉亚。
在第二个测试用例中,一个可能的操作顺序是:
- 第一秒,蕾米莉亚移动到 $$$1$$$,然后灵梦移动到 $$$2$$$.
- 第二秒,蕾米莉亚无法移动,只能原地不动,然后灵梦移动到 $$$1$$$ 并抓住了雷米莉亚。