This is the hard version of the problem. The difference between the versions is that in this version, $0\leq l\leq r \lt 2^{30}$. You can hack only if you solved all versions of this problem.

You are given two integers $l$ and $r$ ($l\le r$).

Let $n = r - l + 1$. We will create two arrays $a$ and $b$, both consisting of $n$ integers. Initially, both $a$ and $b$ are equal to $[l, l+1, \ldots, r]$. You have to reorder the array $a$ arbitrarily to maximize the following value:

$$\sum_{i=1}^n \left (a_i\;|\;b_i \right ).$$

Here, $|$ denotes the bitwise OR operation.

You also need to construct a possible way to reorder the array $a$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains two integers $l$ and $r$ ($0\leq l \leq r \lt 2^{30}$) — the minimum and maximum elements in $a$.

Let $n = r - l + 1$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, print a single integer in the first line of output — the maximum value of $\sum\limits_{i=1}^n \left (a_i\;|\;b_i \right )$.

Then, print $n$ distinct integers $a_1, a_2, \ldots,a_n$ in the second line — the array $a$ after reordering.

If there are multiple answers, you may print any of them.

Note

In the first test case, the reordered array $a$ is $[3,2,1,0]$. The value of the expression is $(3\;|\;0)+(2\;|\;1)+(1\;|\;2)+(0\;|\;3)=3+3+3+3=12$. It can be proved that this is the maximum possible value of the expression.

In the second test case, the reordered array $a$ is $[7,8,5,4,3,2,9,0,1,6]$. The value of the expression is $90$. It can be proved that this is the maximum possible value of the expression.

In the third test case, it can be proved that $240$ is the maximum possible value of the expression.

In the fourth test case, the reordered array $a$ is $[10,8,7,6,9]$. The value of the expression is $(10\;|\;6)+(8\;|\;7)+(7\;|\;8)+(6\;|\;9)+(9\;|\;10)=14+15+15+15+11=70$. It can be proved that this is the maximum possible value of the expression.