Luego de su increíble viaje por algún lugar del Caribe, Ricardo encontró un pomo lleno de frijoles negros mágicos. Ricardo notó que había ~10^6~ frijoles, además que cada número entre ~1~ y ~10^6~ estaba escrito exactamente una vez en algún frijol del frasco.

Ricardo, con sus grandes conocimientos sobre biología, se percató que algunos pares de frijoles negros mágicos cumplían que al juntarse podían condensar el acetil-CoA y el oxalacetato. Luego de muchas investigaciones se dio cuenta que tenían que ver con los números escritos en los respectivos frijoles; más concretamente, un par de frijoles negros mágicos con números ~a~ y ~b~ respectivamente cumple la propiedad si:

$$\displaystyle gcd(a,b)=a\oplus b $$

donde ~a\oplus b~ denota la operación XOR bit a bit de ~a~ y ~b~, y ~gcd(a,b)~ es el máximo común divisor entre ~a~ y ~b~.

Tristemente, la investigación de Ricardo se vio detenida por una misteriosa enfermedad que azotaba su anónimo país... solo se pudo encontrar entre sus notas la pregunta:

¿Cuántos pares no ordenados* de frijoles negros mágicos cumplen dicha propiedad para los frijoles cuyo número está entre ~l~ y ~r~?

* El par ~(a,b)~ se considera el mismo que ~(b,a)~.

Entrada

La primera línea de entrada contiene un único entero ~q~ (~1 \le q \le 2 \cdot 10^5~), la cantidad de consultas.

Las siguientes q líneas estarán formadas por dos enteros ~l_i~ y ~r_i~ (~1 \le l_i \le r_i \le 10^6~).

Salida

Por cada una de las ~q~ consultas, debe responder con un único número entero, la cantidad de pares no ordenados ~a~ y ~b~ que ~l_i \le a, b \le r_i~ y ~gcd(a,b)=a \oplus b~.

Puntuación

Subtarea	Condiciones	Puntos	Dependencias
~1~	~1 \le l_i \le r_i \le 5000 , 1 \le q \le 100~	~4~	~-~
~2~	~1 \le l_i \le r_i \le 5000~	~20~	~1~
~3~	~l_i = 1~	~15~	~-~
~4~	~1 \le q \le 100~	~15~	~1, 3~
~5~	~-~	~46~	~1, 2, 3, 4~

Ejemplos

Entrada de ejemplo 1

2
3 7
5 13

Salida de ejemplo 1

3
6

Explicacion de ejemplo 1

Para el primer caso de prueba, en el rango de ~[3,7]~ los únicos pares que cumplen esto son: ~(4,5)~, ~(4,6)~, ~(6,7)~.

Entrada de ejemplo 2

3
1 23
3 3
25 27

Salida de ejemplo 2

20
0
1

Entrada de ejemplo 3

4
11 83
44 63
39 40
65 65

Salida de ejemplo 3

89
25
0
0

Entrada de ejemplo 4

5
42 189
850 850
840 861
408 525
511 878

Salida de ejemplo 4

208
0
28
167
585

Nota

La operación XOR de dos números ~a~ y ~b~ se define como sigue.

Definamos ~A~ como la representación en base ~2~ de ~a~, ~B~ como la representación en base ~2~ de ~b~ y ~C~ como la representación en base ~2~ del resultado. El valor de ~C~ se calcula de la siguiente forma:

$$\displaystyle C_i= \begin{cases} 1 & \text{si } A_i \neq B_i,\\ 0 & \text{si } A_i = B_i. \end{cases} $$

Por ejemplo, sean los números ~6~ y ~9~. En base ~2~ son ~110_2~ y ~1001_2~ respectivamente. Al realizar la operación XOR obtenemos como resultado ~1110_2~, lo cual es igual a ~14~.