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:

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Constructive algorithms

Complete search

Mathematics

Ad-hoc


Solutions:
p = 10 ** 9 + 7
for i in range(int(input())):
	(l, r) = map(int, input().split())
	t = l + 1 & ~1
	if t >= r:
		print(0, r - l + 1)
		continue
	(K, m, C) = (1, 2, 0)
	while True:
		(t, m2) = (l, m << 1)
		if l & m:
			t = l + m2 & ~(m2 - 1)
		elif l & K:
			t = l | K
		if t + m > r:
			break
		(K, m) = (K << 1 | 1, m2)
	if K == 1:
		C = r - l + 1 - l % 2 >> 1 << 1
	else:
		(t, m2, m) = (l & ~K, m, m >> 1)
		while t | m <= r:
			s = t + m - 1
			if t >= l:
				C = (C + min(m, r - s) * m) % p
			t += m2
			if s >= l and s | m <= r:
				C = (C + min(m, s - l + 1) * m) % p
	print(K, C * 2 % p)