CF2228B.Remilia Plays Soku

Remilia is trying to escape, while Reimu wants to land the final hit.

The playing field consists of $n$ positions arranged in a circle. For each $1 \le i \lt n$, positions $i$ and $i+1$ are adjacent, and positions $1$ and $n$ are also adjacent.

Initially, at time $0$, Reimu is at position $x_1$ and Remilia is at position $x_2$, where $x_1 \ne x_2$.

Each second, the following happens in order:

1. Remilia either moves to an adjacent position or stays in place. Over the entire game, she may move to an adjacent position at most $k$ times.
2. After observing Remilia's action, Reimu either moves to an adjacent position or stays in place.
3. If they are at the same position after both actions, Reimu catches Remilia and the game ends.

Assuming both players play optimally, Reimu always tries to minimize the catching time, while Remilia tries to maximize it.

Find the number of seconds until Reimu catches Remilia.

蕾米莉亚试图逃脱，而灵梦则希望给予最后一击。

游戏场地由 $n$ 个位置构成一个环形。对每个 $1 \le i < n$，位置 $i$ 与 $i+1$ 相邻，且位置 $1$ 与 $n$ 也相邻。

初始时刻（时间为 $0$），灵梦位于位置 $x_1$，蕾米莉亚位于位置 $x_2$，其中 $x_1 \ne x_2$。

每秒内，以下事件按顺序发生：

1. 蕾米莉亚选择移动到一个相邻位置，或原地不动。在整个游戏中，她最多只能向相邻位置移动 $k$ 次。
2. 在观察到蕾米莉亚的动作后，灵梦选择移动到一个相邻位置，或原地不动。
3. 若双方在各自动作完成后处于同一位置，则灵梦成功捕获蕾米莉亚，游戏结束。

假设双方均采取最优策略：灵梦始终力求最小化捕获所需时间，而蕾米莉亚则力求最大化该时间。

求灵梦捕获蕾米莉亚所需的秒数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains four integers $n$, $x_1$, $x_2$ and $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$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \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$）。

For each test case, output the number of seconds until Reimu catches Remilia, assuming both players play optimally.

对于每个测试用例，输出蕾米莉亚被灵梦抓住所需的秒数（假设双方均采取最优策略）。

In the first test case, one possible sequence of actions is:

• In the first second, Remilia stays in place, and then Reimu moves to $2$ and catches Remilia.

In the second test case, one possible sequence of actions is:

• In the first second, Remilia moves to $1$, and then Reimu moves to $2$.
• In the second second, Remilia cannot move and has to stay in place, and then Reimu moves to $1$ and catches Remilia.

在第一个测试用例中，一种可能的操作序列为：

• 第一秒，蕾米莉亚保持不动，随后灵梦移动到位置 $2$ 并抓住蕾米莉亚。

在第二个测试用例中，一种可能的操作序列为：

• 第一秒，蕾米莉亚移动到位置 $1$，随后灵梦移动到位置 $2$。
• 第二秒，蕾米莉亚无法移动，只能保持在原地，随后灵梦移动到位置 $1$ 并抓住蕾米莉亚。