线段树是一种二叉树，它的每个节点都可以覆盖一个区间。线段树中的节点是叶子节点当且仅当它仅覆盖一个位置（即其区间仅包含一个整数）。对于覆盖区间 $[a, b]$ 的非叶子节点，其左子节点的区间为 $[a, \lfloor \frac{a+b}{2} \rfloor]$，右子节点的区间为 $[\lfloor \frac{a+b}{2} \rfloor + 1, b]$。因此，当我们知道根节点的覆盖区间 $[1, n]$ 时，就可以唯一地确定该线段树的结构。

可以证明，对于给定的区间 $[l, r]$，只有一种华丽覆盖（gorgeous-cover）方式，我们将其记为 $w[l, r]$，它表示覆盖 $[l, r]$ 所需的最少区间数量。

例如，在这棵 $[1, 10]$ 的线段树中，$w[3, 6] = 3$。被选中的区间已被涂成红色（$[3, 3]$，$[4, 5]$，$[6, 6]$）。

给定 $n, l, r, k$，你需要在 $[1, n]$ 线段树中找到一个最短的区间 $[l', r']$，满足 $l' \le l \le r \le r'$ 且 $w[l', r'] \le k$。保证 $k \le w[l, r]$。

输入格式

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

接下来的 $T$ 行，每行包含 4 个整数 $n, l, r, k$ ($1 \le l \le r \le n \le 10^{18}$，$1 \le k \le w[l, r]$)。

输出格式

对于每个测试用例，在一行中输出一个整数，表示最短区间的长度。注意，区间 $[l, r]$ 的长度为 $r - l$。

样例

输入样例 1

2
10 3 6 1
10 2 6 3

输出样例 1

9
5