Sea P(x) la mayor potencia de dos que es menor o igual a la raíz cuadrada de ~x~, para cualquier entero ~x > 0~.

Ejemplos:

• P (~9~) = ~2~, porque la raíz cuadrada de ~9~ es ~3~, y la mayor potencia de dos menor o igual a ~3~ es ~2~.

• P (~16~) = ~4~, porque la raíz cuadrada de ~16~ es ~4~, y la mayor potencia de dos menor o igual a ~4~ es ~4~.

• P (~255~) = ~8~, porque la raíz cuadrada de ~255~ es ~15.96871...~, y la mayor potencia de dos menor o igual a ~15.96871...~ es ~8~.

Sea M (~a, b~) la suma de todos los P (~i~), donde ~1 \leq a \leq i \leq b \leq 10^9~.

Escriba un programa que calcule M (~a, b~).

Entrada

La primera línea de la entrada contiene el número de casos de prueba ~t~, donde ~0 \leq t \leq 10^3~. Cada caso de prueba está en una línea propia que contiene dos números enteros ~a~ y ~b~.

Salida

Para cada caso de prueba en la entrada, imprima M (~a, b~) en una sola línea.

Ejemplo de Entrada

2
1 10
100 200

Ejemplo de Salida

17
808