该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

这一天，杰瑞又在汤姆的碗里偷奶酪。汤姆气得追了上去，杰瑞哧溜一下钻进了墙上的​环形通风管道​。

管道里一共有 n 个格子，排成一个圆圈。 汤姆堵在其中一个格子，杰瑞躲在另一个格子里，两者相距不远。

杰瑞心里偷笑：“嘻嘻，这管道窄是窄，但我能往前往后跑，大不了原地不动气死你。” 不过汤姆也不是吃素的，他早就数过：杰瑞今天已经跑了一整天，​最多只能再移动 k步（原地转圈不算步数）。

每一秒的流程如下：

1. 杰瑞先动：可以向左、向右一格，或不动。 （但整场游戏总移动次数不能超过 k 次）
2. 汤姆看到杰瑞的动作后，立刻决定自己向左、向右一格，或不动。
3. 如果汤姆和杰瑞到了同一个格子，汤姆一把按住杰瑞，游戏结束。

汤姆想尽快抓住杰瑞，杰瑞想尽量晚被抓。 两人都是老对手了，每一步都算得清清楚楚。

题目描述

给定 n,x1,x2,k：

• n：环形管道格子数
• x1：汤姆（猫）的初始位置
• x2：杰瑞（老鼠）的初始位置
• k：杰瑞最多还能移动的总步数（相邻移动算 1 步，停留不算）

双方最优策略下，求汤姆抓住杰瑞所需的秒数。

Format

输入格式

第一行一个整数 t（1≤t≤104），表示测试用例数。

接下来 t 行，每行四个整数 n,x1,x2,k：

• 2≤n≤108
• 1≤x1,x2≤n
• x1≠x2
• 0≤k≤108

输出格式

对于每个测试用例，输出一行一个整数，表示抓住所需的最少秒数（在杰瑞抵抗最大的情况下）。

样例

4
2 1 2 0
4 3 2 1
4 2 3 1
16 8 4 2

1
2
2
6

提示（趣味版）

• 样例1：杰瑞已经累得一步都动不了，汤姆直接伸手就抓住了。
• 样例2：杰瑞先挪一步到1，汤姆跳到2；第二秒杰瑞动不了，汤姆从2跳到1抓住。
• 样例3：类似剧情，需要2秒。
• 样例4：两人在环形管道里你追我闪，杰瑞用尽2步拖延，最终汤姆在第6秒得手。

Limitation

1s, 1024KiB for each test case.