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≤T≤100) representando la cantidad de casos de prueba. Por cada caso de prueba hay una línea con dos enteros A y B (1≤A≤B≤1016) 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