在当地的一家乒乓球俱乐部里，有 $n$ 张球台，编号从 $1$ 到 $n$，以及 $2n$ 名选手。

今天，俱乐部将举行一场包含 $k$ 轮的比赛。在每一轮中，恰好同时进行 $n$ 场比赛：在每张球台，恰好有两名选手进行一场比赛。在除最后一轮外的每一轮结束后，选手们按如下规则更换球台：

• 在球台 $i$ 获胜的选手移动到球台 $i + 1$，除非 $i = n$；在这种情况下，该选手留在当前球台。
• 在球台 $i$ 落败的选手移动到球台 $i - 1$，除非 $i = 1$；在这种情况下，该选手留在当前球台。

Alice 和 Bob 是朋友，他们都参加了这次比赛，并分别在球台 $a$ 和 $b$ 进行他们的第一场比赛。在 $k$ 轮比赛的过程中，他们可能会多次相遇并相互对局。

由于他们喜欢互相切磋，他们问你：“在这场比赛中，我们在同一张球台相遇并对局的最大可能次数是多少？”请帮助他们！

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。

接下来的 $t$ 行中，每行包含四个整数 $n, k, a, b$ ($1 \le a, b \le n \le 10^9$, $1 \le k \le 10^9$)，表示有 $n$ 张球台，比赛进行 $k$ 轮，Alice 从球台 $a$ 开始，Bob 从球台 $b$ 开始。

输出格式

对于每个测试用例，输出一个整数：在 $k$ 轮比赛中，Alice 和 Bob 之间可能发生的最大对局次数。

样例

输入样例 1

3
7 4 2 6
7 5 2 6
4 3 1 4

输出样例 1

1
2
1