Matcom Online Grader

ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.

The 2023 ICPC Caribbean Finals (Qualifier) - Warmup1

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

C - Contando unos

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Fito quiere saber dado dos números

A $A$ y

B $B$ la cantidad de 1s que hay en la representación binaria de todos los enteros que están en el intervalo

[A,B] $[A, B]$ .

Input

La primera línea de la entrada es un entero

T $T$

(1≤T≤100) $(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 $A$ y

B $B$

(1≤A≤B≤1016) $(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 $1$ que hay en la representación binaria de todos los enteros que hay en el intervalo

[A,B] $[A, B]$ .

Sample test(s)

Input

2 2 101 1202 110011

Output

322 897255