8657: Simple Math 4

Given nonnegative integers N,L,Rand X find the maximum value of 

∑i=1NAi 

over all possible integer arrays A of length N satisfying

1. A1⊕A2⊕⋯⊕AN=X, where $\oplus$ denotes the bitwise exclusive-or operation;
2. $\forall 1\le i\le N$,L≤Ai≤R.

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

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≤N≤109, 0≤L≤R≤109, 0≤X≤109).