Trailing Zeros Query

We define a function \(f(x)\) as the position of the lowest 1 in the binary representation of \(x\), where the least significant bit is considered at position \(0\). In other words, \(f(x)\) is the number of trailing zeros in the binary representation of \(x\). The following C++ function computes \(f(x)\):

int f(int x){
    int ans = 0;
    while(x % 2 == 0){
        x /= 2;
        ans += 1;
    }
    return ans;
}

You are given \(T\) test cases. Each test case consists of an interval \([l, r]\). For each test case, count how many integers \(i\) in the interval \(l \le i \le r\) satisfy \(f(i) < f(i+1)\).

Hint: Notice that for any even integer \(i\), \(f(i)\) is at least 1 while \(f(i+1)\) for the subsequent odd number is always \(0\). Hence, the condition \(f(i) < f(i+1)\) holds only when \(i\) is odd.

The answer for each test case is thus the number of odd numbers in the interval \([l, r]\). You can compute it using the formula:

[ \text{Answer} = \left\lfloor \frac{r+1}{2} \right\rfloor - \left\lfloor \frac{l}{2} \right\rfloor ]

inputFormat

The first line contains a single integer \(T\) (the number of test cases).

Each of the next \(T\) lines contains two space-separated integers \(l\) and \(r\) representing an interval.

outputFormat

For each test case, output a single integer on a new line: the count of integers \(i\) in \([l, r]\) satisfying \(f(i) < f(i+1)\).

sample

1
1 1

1