Problem Description

Given nonnegative integers $N,L,R$ and $X$, find the maximum value of $\sum_{i=1}^N A_i$ over all possible integer arrays $A$ of length $N$ satisfying

<ol>
<li> $ A_1 \oplus A_2 \oplus \dots \oplus A_N = X$, where $\oplus$ denotes the bitwise exclusive-or operation; </li>
<li> $\forall 1 \le i \le N$, $L \le A_i \le R$. </li>
</ol>

If there exists no valid array $A$ satisfying above requirements, output $-1$.

Input

The first line contains an integer $T$. ($1 \le T \le 3000$), denoting the number of test cases.

For each test case, there is a line containing integers $N,L,R,X(1 \leq N \leq 10^9$, $0 \leq L \leq R \le 10^9$, $0 \leq X \leq 10^9)$.

Output

For each test case, output an integer in a line, denoting the answer.

1
5 890 970 768

4756