给定非负整数 $N, L, R$ 和 $X$，求满足以下条件的长度为 $N$ 的整数数组 $A$ 中，$\sum_{i=1}^N A_i$ 的最大值：
- $\bigoplus_{i=1}^N A_i = X$，其中 $\oplus$ 表示异或运算。
- $\forall 1 \le i \le N, L \le A_i \le R$。
如果不存在满足上述要求的有效数组 $A$，输出 $-1$。
第一行包含一个整数 $T$ ($1 \le T \le 3000$)，表示测试用例的数量。 对于每个测试用例，包含一行整数 $N, L, R, X$ ($1 \le N \le 10^9, 0 \le L \le R \le 10^9, 0 \le X \le 10^9$)。
对于每个测试用例，输出一行一个整数，表示答案。
样例
输入格式 1
1 5 890 970 768
输出格式 1
4756