你是否厌倦了在编程竞赛中解决那些枯燥的双人博弈问题？别担心，这一次，Chou 老师和 Tseng 老师正在玩一个真正有趣的游戏！

游戏在一个长长的白板上进行。初始时，白板上写着 $N$ 个介于 $L$ 和 $R$ 之间的整数 $a_1, \dots, a_N$。两位老师轮流进行操作，Chou 老师先手。在每一轮中，玩家可以“收集”当前白板上的一个整数 $x$。然后，他需要将选中的整数 $x$ 从白板上移除，并将剩余的每个整数 $y$ 替换为它们与 $x$ 的绝对差值。换句话说，每个整数 $y$ 被替换为 $|x - y|$。注意，如果白板上有多个等于 $x$ 的整数，则仅移除其中一个，其余的将被替换为零。

游戏将在 $N$ 轮后结束，届时白板上的所有整数都将被移除。此时，两位老师将计算各自在整个游戏过程中收集到的整数之和。自然地，Chou 老师的目标是最大化他与 Tseng 老师的得分差，反之亦然。等价地，由于他们的目标之和为零，他们将游戏的得分定义为 Chou 老师的总和减去 Tseng 老师的总和，Chou 老师希望最大化该得分，而 Tseng 老师希望最小化该得分。

起初，这个游戏只是两位老师在在线竞赛结束后，在还有超过一小时空闲时间时用来消磨时间的娱乐活动。然而，由于两位老师的名气，加上这个游戏确实非常有趣，他们之间的对局变得越来越受欢迎，人们甚至开始对比赛结果进行下注。

你是老师的学生，因此他们总是让你在比赛开始前写下初始的 $N$ 个数字来布置游戏。为了利用他们的信任，你想通过操纵比赛结果来获利。你已经知道，由于老师们极其聪明，他们总是会做出最优决策以最大化各自的目标。你还选择了 $C$ 作为游戏的最终得分进行下注。现在，为了让结果如你所愿，你计划在老师们到来之前秘密地修改初始白板上的一些数字。显然，你填写的数字只能是 $L$ 到 $R$ 之间的整数，否则老师们会立即发现。你还希望尽可能减少修改次数，以降低被发现的风险。

你需要修改初始白板上最少多少个整数，才能使游戏的最终得分成为你下注的 $C$？

输入格式

第一行包含测试用例的数量 $T$。

每个测试用例由两行输入组成。第一行包含四个整数 $N, L, R$ 和 $C$，用空格分隔 ($1 \le N \le 10^6; 1 \le L \le R \le 10^9; |C| \le 10^{18}$)。第二行包含 $N$ 个整数 $a_1, \dots, a_N$ ($L \le a_i \le R$)。

所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数：使游戏最终得分变为 $C$ 所需的最少修改次数。如果无法做到，则输出 $-1$。

样例

输入 1

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

输出 1

1
0
1
1
-1