Potencias Cuadradas


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Python

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

Comments

There are no comments at the moment.