Read problems statements in Mandarin Chinese and Russian.

Let's consider a square matrix of size N × N, where N = R −­­­­­­­­­­­ L + 1. We will enumerate the columns of this matrix with consecutive integers from L to R (the leftmost column will be assigned number L and the rightmost - number R). In similar manner we will enumerate rows with the same integers (the top row will be assigned number L and the bottom row - number R).

Every cell of this matrix has an integer written inside it. The cell at the intersection of row X and column Y has integer (X xor Y) written inside.

Two cells are called adjacent if and only if they have a common side. That way every inner cell have 4 neighbors and any of four corner cells have 2 neighbors.

A walk is a sequence of cells C_{0}, C_{1}, C_{2}, ..., C_{K}, where for every 1 ≤ i ≤ K the cells C_{i-1} and C_{i} are adjacent and for every 0 ≤ j ≤ K the number written inside cell C_{j} is equal j. The number K is the length of that walk.

Your task is for given L and R values, find the maximal possible value of K, as well as the count C of different walks with that maximal length. As the value of C could be very large, output it modulo (10^{9} + 7).

------ Input ------

The first line of the input contains an integer T denoting the number of test cases.

The description of T test cases follows.

For each test case, the only line of input contains two integers L and R.

------ Output ------

For each test case, output a single line containing two integers K and C.
The value of C should be printed modulo (10^{9} + 7).

------ Constraints ------

$1 ≤ T ≤ 20 000$
$1 ≤ L ≤ R ≤ 10^{18}$

------ Subtasks ------

$Subtask #1: 1 ≤ T ≤ 500; 0 ≤ R - L ≤ 300 (8 points)$
$Subtask #2: original constraints, only the value of K will be checked. (24 points)$
$Subtask #3: original constraints (68 points)$

----- Sample Input 1 ------
4

1 1

1 2

1 3

2 3
----- Sample Output 1 ------
0 1

0 2

3 4

1 4
----- explanation 1 ------
Example case 1. The matrix contains just one cell, so, there is no possibility to make a single move, thus K = 0. We have just one possibility - to start the walk at the only cell and to end it immediately.

Example case 2. The matrix doesn't contains a cell with number one inside, so, there once again is no possibility to make a single move, thus K = 0. Our walk is just a single cell with number zero inside and there are two such cells, thus C = 2. The matrix in this case looks like this:

(1 xor 1) (1 xor 2) = 0 3
(2 xor 1) (2 xor 2) = 3 0

Example case 3. The four possible walks are:

Example case 4. The four possible walks are:

见题面

见题面