B. Remilia Plays Soku
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$).

Output

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

Example
Input
4
2 1 2 0
4 3 2 1
4 2 3 1
16 8 4 2
Output
1
2
2
6
Note

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.