B - Contando unos

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Fito quiere saber dado dos números $A$ y $B$ la cantidad de 1s que hay en la representación binaria de todos los enteros que están en el intervalo $[A, B]$.

Input

La primera línea de la entrada es un entero $T$ $(1 \leq T \leq 100)$ representando la cantidad de casos de prueba. Por cada caso de prueba hay una línea con dos enteros $A$ y $B$ $(1 \leq A \leq B \leq 10^{16})$ separados por un espacio.

Output

Por cada caso de prueba se imprime en una línea la cantidad de dígitos $1$ que hay en la representación binaria de todos los enteros que hay en el intervalo $[A, B]$.

Sample test(s)

Input
2 2 101 1202 110011
Output
322 897255